Java DFS only using Map beats 99%


  • 0
    Y

    class Solution {

    public String countOfAtoms(String formula) {
        TreeMap<String, Integer> map = new TreeMap<>();
        dfsHelper(formula, 0, formula.length() - 1, 1, map);
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            sb.append(entry.getKey());
            if (entry.getValue() > 1) {
                sb.append(entry.getValue());
            }
        }
        return sb.toString();
    }
    private void dfsHelper(String formula, int start, int end, int times, Map<String, Integer> map) {
        if (start > end) {
            return;
        }
        while (start <= end) {
            if (formula.charAt(start) == '(') {
                int rightParenIdx = findRightParen(formula, start, end);
                int[] res = findNum(formula, rightParenIdx + 1, end);
                dfsHelper(formula, start + 1, rightParenIdx - 1, times * res[0], map);
                start = res[1];
            } else if (formula.charAt(start) >= 'A' && formula.charAt(start) <= 'Z') {
                int temp = start + 1;
                while (temp <= end && formula.charAt(temp) >= 'a' && formula.charAt(temp) <= 'z') {
                    temp++;
                }
                String atom = formula.substring(start, temp);
                int[] res = findNum(formula, temp, end);
                map.put(atom, map.getOrDefault(atom, 0) + res[0] * times);
                start = res[1];
            }
        }
    }
    
    private int findRightParen(String formula, int start, int end) {
        int count = 0;
        while (start <= end) {
            if (formula.charAt(start) == '(') {
                count++;
            } else if (formula.charAt(start) == ')') {
                count--;
            }
            if (count == 0) {
                return start;
            }
            start++;
        }
        return -1;
    }
    
    private int[] findNum(String formula, int start, int end) {
        int[] res = new int[2];
        if (start > end || formula.charAt(start) < '0' || formula.charAt(start) > '9') {
            res[0] = 1;
            res[1] = start;
            return res;
        }
        while (start <= end && formula.charAt(start) >= '0' && formula.charAt(start) <= '9') {
            res[0] = res[0] * 10 + formula.charAt(start) - '0';
            start++;
        }
        res[1] = start;
        return res;
    }
    

    }


Log in to reply
 

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