241. Different Ways to Add Parentheses.md

Solution1 (optimized with memoization)

class Solution {
    Map<String, List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String left = input.substring(0, i);
                String right = input.substring(i + 1);
                List<Integer> leftOprds = map.containsKey(left) ? map.get(left) : diffWaysToCompute(left);
                List<Integer> rightOprds = map.containsKey(right) ? map.get(right) : diffWaysToCompute(right);
                for (Integer leftOprd : leftOprds) {
                    for (Integer rightOprd : rightOprds) {
                        if (c == '+') {
                            res.add(leftOprd + rightOprd);
                        }
                        else if (c == '-') {
                            res.add(leftOprd - rightOprd);
                        }
                        else {
                            res.add(leftOprd * rightOprd);
                        }
                    }
                }
            }
        }
        if (res.size() == 0) {
            int operand = Integer.valueOf(input);
            res.add(operand);
        }
        map.put(input, res);
        return res;
    }
}

note

• time O(2^n (n is the number of operators in input)) space O(n)
• The idea is to apply divide-and-conquer thinking to recursively solve the problem. The key point here is to look for operators. We iterate through the string and for each operator we find, we know that its left and right strings are its operands. So we could recursively call the function itself and pass these two substrings as its new parameters.
• We also optimized the recursion with memoization using hashmap.