A readable Python solution


  • 0
    F

    The chemical formula follows the pattern of Atom/Number/Atom/Number... for example H20. If there is no number, the default is 1.
    Also the pattern can be '(' formula ')' /Number, for example, Mg(OH)2.
    With that, we can write structured code:

    def countOfAtoms(self, formula):
            # read a number
            def read_num(formula, i):
                num = 0
                while i < len(formula) and formula[i].isdigit():
                    num = 10 * num + int(formula[i])
                    i += 1
                if num == 0:
                    num = 1
                return num, i
    
            # read an Atom, a upper letter followed by several  lower case letters
            def read_atom(formula, i):
                atom = formula[i]
                i += 1
                while i < len(formula) and formula[i].islower():
                    atom += formula[i]
                    i += 1
                return atom, i
    
            # read the formula inside parentheses
            def read_formula(formula, i):
                from collections import defaultdict
                atoms = defaultdict(int)
                while i < len(formula) and formula[i] != ')':
                    if formula[i] == '(':
                        child_atoms, i = read_formula(formula, i + 1)
                        num, i = read_num(formula, i)
                        for k, v in child_atoms.items():
                            atoms[k] += v*num
                    else:
                        atom, i = read_atom(formula, i)
                        num, i = read_num(formula, i)
                        atoms[atom] += num
                return atoms, i + 1
           
            i = 0
            atoms, i = read_formula(formula, i)
            result = ''
            for atom, num in sorted(atoms.items()):
                result += atom
                if num > 1:
                    result += str(num)
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.