Python solution using recursion and regex


  • 2

    A given formula can either start with '(' or an atom.
    case 1: If it starts with an atom, then we extract the starting atom and its count using regex and handle the rest of the formula recursively
    case 2: If it starts with a '(', then we find the matching ')' and use recursion twice
    a) First we solve the sub formula inside '(' ')' using recursion and we extract the count following it and update the counts.
    b) Then for the remainder of the formula we make a recursive call to solve it.

        def countOfAtoms(self, formula):
            res_dict = defaultdict(int)
            self.count_rec(formula, res_dict)
            return ''.join(chain.from_iterable([[atom, str(res_dict[atom]) if res_dict[atom] > 1 else ''] for atom in sorted(res_dict.keys())]))
    
        def count_rec(self, formula, res):
            if formula is None or len(formula) == 0:
                return
            if formula[0] == '(':
                count, i = 1, 1
                while count != 0:
                    if formula[i] == '(': count += 1
                    if formula[i] == ')': count -= 1
                    i += 1
                temp_res = defaultdict(int)
                self.count_rec(formula[1:i-1], temp_res)
                num = re.findall('^\d+', formula[i:])
                if len(num) > 0:
                    num = int(num[0])
                    i += len(str(num))
                else:
                    num = 1
                for atom in temp_res:
                    res[atom] += temp_res[atom] * num
                self.count_rec(formula[i:], res)
            else:
                atom = re.findall('[A-Z][a-z]*', formula)[0]
                num = re.findall('^\d+', formula[len(atom):])
                num = int(num[0]) if len(num) > 0 else 1
                res[atom] += num
                self.count_rec(formula[len(atom) + (0 if num == 1 else len(str(num))):], res)
    

Log in to reply
 

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