Clean Java solution with stack and tree map (10ms)


  • 0
    S

    The key is to maintain a multiplier with a stack by working from the end of the string to the beginning.

    class Solution {
        public String countOfAtoms(String formula) {
            TreeMap<String, Integer> map = new TreeMap<>();
            int mul = 1;
            Deque<Integer> stack = new ArrayDeque<>();
            int i = formula.length() - 1;
            while(i >= 0) {
                int d = 0;
                int cur = 0;
                while(Character.isDigit(formula.charAt(i))) {
                    cur = cur + (formula.charAt(i) - '0') * (int)Math.pow(10, d);
                    d++;
                    i--;
                }
                if(formula.charAt(i) == ')') {
                    if(cur > 0) {
                        mul *= cur;
                        stack.push(cur);
                    }
                    else {
                        stack.push(1);
                    }
                    i--;
                }
                else if(formula.charAt(i) == '(') {
                    mul /= stack.pop();
                    i--;
                }
                else {
                    int end = i + 1;
                    while(formula.charAt(i) >= 'a' && formula.charAt(i) <= 'z') {
                        i--;
                    }
                    String atom = formula.substring(i, end);
                    map.put(atom, map.getOrDefault(atom, 0) + mul * (cur > 0 ? cur : 1));
                    i--;
                }
            }
            StringBuilder sb = new StringBuilder();
            for(String atom : map.keySet()) {
                sb.append(atom);
                if(map.get(atom) > 1) {
                    sb.append(map.get(atom));
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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