_726. Number of Atoms.md

726. Number of Atoms

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 14, 2024

Last updated : July 14, 2024

---

Related Topics : Hash Table, String, Stack, Sorting

Acceptance Rate : 65.185 %

---

Initial thought process

• Use regex: re.findall('[A-Z][a-z]\d+', formula) to find all elements and their pairings
• Won't work cause of brackets
• Recursive call for the case of brackets

Later

• Could separate the formula into multiple layers of lists of lists
• Each time a bracket is found, let that element be a tuple[list, int] where the list is the inside case and the int is the multiplier
• Similar to the LinkedList question with "optional" nodes where it branches off, we can recursivly find this then recursively merge all the solutions

Final

• Recursively call the bracketed portions (find the indices using a counter and call)
• Calculate the multipliers and track counters
• Have to use if else cases to take care of the 2-letter and 1-letter elements
• Add the counters with a frequency multiplier

---

Solutions

• h726 Daily v1 RECURSIVE.py
• h726 Daily v2 RECURSIVE More Abstraction and Less Indents.py

Python

h726 Daily v1 RECURSIVE.py

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        def helper(formula: str) -> Counter :
            output = Counter()
            indx = 0

            while indx < len(formula) :

                # Bracketed portion so recurs it
                if formula[indx] == '(' :

                    # Find ending of this bracket
                    endIndx = indx
                    openCount = 1
                    while openCount > 0 :
                        endIndx += 1
                        if formula[endIndx] == ')' :
                            openCount -= 1
                        elif formula[endIndx] == '(' :
                            openCount += 1

                    # Recurs
                    cnt = helper(formula[indx + 1 : endIndx])

                    # Get multiplier e.g. (He2O4)6 multiplier would be 6
                    multiplier = 0
                    indx = endIndx + 1
                    while indx < len(formula) and re.match('\d', formula[indx]) :
                        multiplier = multiplier * 10 + int(formula[indx])
                        indx += 1

                    # If nothing, defaults to 1 instance
                    multiplier = max(multiplier, 1)

                    for el, freq in cnt.items() :
                        output[el] += freq * multiplier

                # Element found
                else :
                    el = ''
                    
                    # 2 letter element
                    if re.match('[A-Z][a-z]', formula[indx : min(indx + 2, len(formula))]) :
                        el = formula[indx : indx + 2]
                        indx += 2
                    # 1 letter element
                    else :
                        el = formula[indx]
                        indx += 1

                    # If next isn't number
                    if indx >= len(formula) \
                        or re.match('[A-Z]', formula[indx]) \
                        or formula[indx] == '(' :
                        output[el] += 1
                    # If is number, find count
                    else :
                        cnt = 0
                        while indx < len(formula) and re.match('\d', formula[indx]) :
                            cnt = 10 * cnt + int(formula[indx])
                            indx += 1
                        output[el] += cnt
            # Helper output
            return output

        return ''.join(sorted([f'{el}{freq}' if freq > 1 
                                             else el for el, freq in helper(formula).items()]))

h726 Daily v2 RECURSIVE More Abstraction and Less Indents.py

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        return ''.join(sorted([f'{el}{freq}' if freq > 1 
                                             else el for el, freq in self.helper(formula).items()]))

    def getEndIndx(self, formula, indx) -> int :
        openCount = 1
        while openCount > 0 :
            indx += 1
            if formula[indx] == ')' :
                openCount -= 1
            elif formula[indx] == '(' :
                openCount += 1
        return indx

    def getNumber(self, formula, indx) -> Tuple[int, int] : # (multiplier, new indx)
        multiplier = 0
        while indx < len(formula) and re.match('\d', formula[indx]) :
            multiplier = 10 * multiplier + int(formula[indx])
            indx += 1
        
        return (max(multiplier, 1), indx)


    def helper(self, formula: str) -> Counter :
        output = Counter()
        indx = 0

        while indx < len(formula) :

            # Bracketed portion so recurs it
            if formula[indx] == '(' :
                # Find ending of this bracket
                endIndx = self.getEndIndx(formula, indx)

                # Recurs
                cnt = self.helper(formula[indx + 1 : endIndx])

                # Get multiplier e.g. (He2O4)6 multiplier would be 6
                multiplier, indx = self.getNumber(formula, endIndx + 1)

                for el, freq in cnt.items() :
                    output[el] += freq * multiplier

            # Element found
            else :
                el = ''
                
                # 2 letter element
                if re.match('[A-Z][a-z]', formula[indx : min(indx + 2, len(formula))]) :
                    el = formula[indx : indx + 2]
                    indx += 2
                # 1 letter element
                else :
                    el = formula[indx]
                    indx += 1

                # If next isn't number
                if indx >= len(formula) \
                    or re.match('[A-Z]', formula[indx]) \
                    or formula[indx] == '(' :
                    output[el] += 1
                # If is number, find count
                else :
                    oldIndx = indx
                    cnt, indx = self.getNumber(formula, indx)
                    output[el] += cnt
        # Helper output
        return output