https://leetcode.com/problems/number-of-atoms/

number-of-atoms.java

/**
Recursion Solution
**/
class Solution {
    public String countOfAtoms(String formula) {
        if (formula == null || formula.length() == 0) {
            return "";
        }
        int len = formula.length();
        Map<String, Integer> res = parse(formula, new int[]{len - 1});
        List<String> atoms = new ArrayList<>(res.keySet());
        Collections.sort(atoms);
        
        StringBuilder sb = new StringBuilder();
        for (String atm : atoms) {
            sb.append(atm);
            int cnt = res.get(atm);
            if (cnt > 1) {
                sb.append(cnt);
            }
        }
        return sb.toString();
    }
    //
    private Map<String, Integer> parse(String str, int[] p) {
        Map<String, Integer> result = new HashMap<>();
        if (p[0] < 0) {
            return result;
        }
        StringBuilder atom = new StringBuilder();
        int num = 0;
        int base = 1;
        while(p[0] >= 0) {
            if (Character.isLetter(str.charAt(p[0]))) {
                atom.append(str.charAt(p[0]));
                // end of current atom, upper case
                if (Character.isUpperCase(str.charAt(p[0]))) {
                    int cnt = num > 0 ? num : 1;
                    String atm = atom.reverse().toString();
                    result.put(atm, result.getOrDefault(atm, 0) + cnt);
                    num = 0;
                    base = 1;
                    atom.setLength(0);
                }
                p[0] --;
            } else if (Character.isDigit(str.charAt(p[0]))) {
                num = (str.charAt(p[0]) - '0') * base + num;
                base *= 10;
                p[0] --;
            } else if (str.charAt(p[0]) == ')') {
                p[0] --;
                Map<String, Integer> sub = parse(str, p);
                int cnt = num > 0 ? num : 1;
                for (Map.Entry<String, Integer> entry : sub.entrySet()) {
                    String key = entry.getKey();
                    int val = entry.getValue();
                    result.put(key, result.getOrDefault(key, 0) + val * cnt);
                }
                num = 0;
                base = 1;
                atom.setLength(0);
            } else if (str.charAt(p[0]) == '(') {
                p[0] --;
                return result;
            }
        }
        return result;
    }
    
    
}