Java recursive 4ms sol with memoization beats 90%


  • 0

    use memoization to make duplicate expression pattern faster

    public class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            if (input == null || input.isEmpty()) {
                return new ArrayList<>();
            }
            return diffWaysToComputeHelper(input, new HashMap<>());
        }
        
        private List<Integer> diffWaysToComputeHelper(String input, Map<String, List<Integer>> memo) {
            if (memo.containsKey(input)) {
                return memo.get(input);
            }
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < input.length(); i++) {
                if (Character.isDigit(input.charAt(i))) {
                    continue;
                }
                List<Integer> leftOperands = diffWaysToComputeHelper(input.substring(0, i), memo);
                List<Integer> rightOperands = diffWaysToComputeHelper(input.substring(i + 1), memo);
                for (int opL : leftOperands) {
                    for (int opR : rightOperands) {
                        switch (input.charAt(i)) {
                            case '+':
                                res.add(opL + opR);
                                break;
                            case '-':
                                res.add(opL - opR);
                                break;
                            case '*':
                                res.add(opL * opR);
                        }
                    }
                }
            }
            if (res.isEmpty()) {// indicating no operator in input, the whole str is operand
                res.add(Integer.parseInt(input));
            }
            memo.put(input, res);
            return res;
        }
    }

Log in to reply
 

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