Different Ways to Add Parentheses LeetCode solution in Java

1
class Solution {
2
  Map<String, List<Integer>> memo = new HashMap<>();
3

4
  public List<Integer> diffWaysToCompute(String expression) {
5
    List<Integer> res = new LinkedList<>();
6
    if (memo.containsKey(expression)) return memo.get(expression);
7

8
    for (int i = 0; i < expression.length(); i++) {
9
      char c = expression.charAt(i);
10
      if (c == '*' || c == '+' || c == '-') {
11
        // divide
12
        List<Integer> left = diffWaysToCompute(expression.substring(0, i));
13
        List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
14

15
        // conquer
16
        for (int a : left) {
17
          for (int b : right) {
18
            if (c == '+') {
19
              res.add(a + b);
20
            } else if (c == '-') {
21
              res.add(a - b);
22
            } else if (c == '*') {
23
              res.add(a * b);
24
            }
25
          }
26
        }
27
      }
28
    }
29
    // base case, when there is no operator
30
    if (res.isEmpty()) {
31
      res.add(Integer.parseInt(expression));
32
    }
33
    memo.put(expression, res);
34
    return res;
35
  }
36
}