Simple Java Solution using Backward Scanning


  • 0
    X

    It is easier if we scan the formula from right to left. Use a stack to record counts while scanning.

    class Solution {
        public String countOfAtoms(String formula) {
            TreeMap<String, Integer> map = new TreeMap<>();
            Deque<Integer> q = new LinkedList<>(); 
            char[] ca = formula.toCharArray();
            int n = ca.length;
            int i = n - 1;
            while (i >= 0) { // Scan from right to left.
                if (ca[i] == '(') {
                    q.pop();
                    
                // If it is a number, multiply it by the top number on stack and then push it to the top of stack.
                } else if (ca[i] >= 48 && ca[i] <= 57) {
                    int j = i;
                    while (ca[i - 1] >= 48 && ca[i - 1] <= 57) {
                        i--;
                    }
                    int num = Integer.parseInt(formula.substring(i, j + 1));
                    num *= q.isEmpty() ? 1 : q.peek();
                    q.push(num);
                    
                // If it is an element, add the count to map and pop a number from the stack only when it is followed by a number.    
                } else if (ca[i] >= 65) {
                    int j = i;
                    while (i >= 0 && ca[i] >= 97) {
                        i--;
                    }
                    String element = formula.substring(i, j + 1);
                    int count = q.isEmpty() ? 1 : q.peek();
                    map.put(element, map.getOrDefault(element, 0) + count);
                    if (j < n - 1 && ca[j + 1] >= 48 && ca[j + 1] <= 57) {
                        q.poll();
                    }
                }
                i--;
            }
            
            StringBuilder builder = new StringBuilder();
            for (Map.Entry<String, Integer> entry : map.entrySet()) {
                builder.append(entry.getKey());
                if (entry.getValue() > 1) {
                    builder.append(entry.getValue());
                }
            }
            return builder.toString();
        }
    }
    

Log in to reply
 

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