Java Solution -no need of counting parentheses


  • 0
    N

    This solution is similar to most recursive solutions. However, it doesn't need scan over the string and count the number of parentheses.

    class Solution {
        public String countOfAtoms(String formula) {
            
            Map<String, Integer> map = new HashMap<>();
            count(formula, 0, map);
            
            List<String> eles = new ArrayList<>(map.keySet());
            Collections.sort(eles);
            StringBuilder sb = new StringBuilder();
            for (String ele : eles) {
                sb.append(ele);
                if(map.get(ele) > 1) {
                    sb.append(map.get(ele));
                }
                
            }
            return sb.toString();
            
        }
        
        private int count(String formula, int start, Map<String, Integer> map) {
            int i=start;
            
            while(i< formula.length()) {
                // System.out.println("the i:" + formula.charAt(i));
                if (formula.charAt(i) == '(') {
                    Map<String, Integer> small = new HashMap<>();
                    int finishedAt = count(formula, i+1, small);
                    i = finishedAt;
                    merge(map, small);
                } else if (formula.charAt(i) == ')') {
                    i++;
                    if (i < formula.length() && Character.isDigit(formula.charAt(i)) ) {
                        int mult = 0;
                        
                        while (i<formula.length() && Character.isDigit(formula.charAt(i))) {
                            mult = mult*10 + (formula.charAt(i)-'0');
                            i++;
                        }
                        mult = Math.max(1, mult);
                        for (String ele : map.keySet()) {
                            map.put(ele, map.get(ele) * mult);
                        }
                        return i;
                    }
                    return i;
                } else {
                    StringBuilder sb = new StringBuilder();
                    sb.append(formula.charAt(i));
                    i++;
                    while(i < formula.length() && Character.isLetter(formula.charAt(i)) && Character.isLowerCase(formula.charAt(i)) ) {
                        sb.append(formula.charAt(i));
                        i++;
                    } 
                    int mult = 0;
                    while (i<formula.length() && Character.isDigit(formula.charAt(i))) {
                        mult = mult*10 + (formula.charAt(i)-'0');
                        i++;
                    }
                    mult = Math.max(1, mult);
                    String e = sb.toString();
                    map.put(e, map.getOrDefault(e, 0) + mult);
                }
            }
            return i;
        }
        
        private void merge(Map<String, Integer> p, Map<String, Integer> k) {
            for (String ele : k.keySet()) {
                p.put(ele, p.getOrDefault(ele, 0) + k.get(ele));
            }
        }
    }
    

Log in to reply
 

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