[Python] Simple Solution with Stack and Map


  • 0
    Y

    Similar idea of equation calculation. Start from right, and use stack to keep track of number. Use pCnt to keep track of count before ), and cnt to keep track of current number. If current char is ) push pCnt* cnt to stack, and if current char is '(', pop number from stack, and update pCnt. If current char is upper case, update map.

    class Solution(object):
        def countOfAtoms(self, formula):
            """
            :type formula: str
            :rtype: str
            """
            import collections
            mp = collections.Counter()
            stk = []
            cnt, pCnt = 1, 1
            prevIdx, idx = len(formula), len(formula) - 1
            while idx >= 0:
                val = formula[idx]
                if val == ')':
                    pCnt *= cnt
                    stk.append(cnt)
                    cnt, prevIdx = 1, idx
                elif val == '(':
                    pCnt /= stk.pop()
                    cnt, prevIdx = 1, idx
                elif val.isdigit():
                    tmpIdx = idx;
                    # Get all digit
                    while tmpIdx >= 0 and formula[tmpIdx].isdigit():
                        tmpIdx -= 1
                    cnt, prevIdx = int(formula[tmpIdx + 1:idx + 1]), tmpIdx + 1
                    idx = tmpIdx + 1
                elif val.isupper():
                    s = formula[idx:prevIdx]
                    mp[s] += cnt * pCnt
                    cnt, prevIdx = 1, idx
                idx -= 1
    
            ans = []
            for key in sorted(mp.keys()):
                val = mp[key]
                if val > 1:
                    ans.extend([key, str(val)])
                else:
                    ans.extend([key])
            return ''.join(ans)
    

Log in to reply
 

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