241. Different Ways to Add Parentheses

```java
class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        Map<String, List<Integer>> memo = new HashMap<>();
        return dfs(expression, memo);
    }
    private List<Integer> dfs(String expression, Map<String, List<Integer>> memo) {
        if (memo.containsKey(expression)) {
            return memo.get(expression);
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1));

                for (int l : left) {
                    for (int r : right) {
                        int calResult = calculate(l, r, c);
                        result.add(calResult);
                    }
                }
            }
        }
        
        if (result.size() == 0) { // no any cal result, so it a pure number expression
            result.add(Integer.parseInt(expression));
        }

        memo.put(expression, result);
        return result;
    }
    private int calculate(int x, int y, char operator) {
        if (operator == '-') {
            return x - y;
        }
        if (operator == '+') {
            return x + y;
        }
        if (operator == '*') {
            return x * y;
        }
        return 0;
    }
}

/*
if we meet "+", "-", "*"
get dfs, left part, right part
for loop cal


2
"-"
1-1 ->   1
         -
         1

2-1    ->    2
"-"          -
1            1

*/
```

T: O(n^3), 我們要記錄n^2個數級的DP，每個DP我們都經歷了分解點。所以時間複雜度大概是N^3

S: O(n)

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        Map<String, List<Integer>> memo = new HashMap<>();
        return dfs(expression, memo);
    }
    private List<Integer> dfs(String expression, Map<String, List<Integer>> memo) {
        List<Integer> result = new ArrayList<>(); // every time get new value
        if (memo.containsKey(expression)) {
            return memo.get(expression);
        }
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                List<Integer> left = dfs(expression.substring(0, i), memo); 
                List<Integer> right = dfs(expression.substring(i+1), memo); 

                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            result.add(l + r);
                        } else if (c == '-') {
                            result.add(l - r);
                        } else if (c == '*') {
                            result.add(l * r);
                        }
                    }
                }
            }
        }
        if (result.isEmpty()) {
            result.add(Integer.valueOf(expression));
        }
        memo.put(expression, result);
        return result;
    }
}

/*
divide and conquer

"2*3-4*5"

2 3 4 5

(2) (3 4 5)

(2 3) (4 5)
...

List<Integer> left
List<Integer> right

for (int l : left) {
    for (int r : right) {
        l op r -> save to result
    }
}


*/

T: O(有多少分割方式) -> O(catalan number) = O(n^2), 因為是像是組合數切割分治
S: O(catalan number): n^2

```java
class Solution {
    Map<String, List<Integer>> memo = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        if (memo.containsKey(expression)) {
            return memo.get(expression);
        }
        List<Integer> result = new ArrayList<>(); // 每層 result 都會 re-new..., 最後傳回當層的幾個 result

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '-' || c == '*' || c == '+') {
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1));
                for (int l : left) {
                    for (int r : right) {
                        if (c == '-') {
                            result.add(l - r);                            

                        } else if (c == '*') {
                            result.add(l * r);
                        } else if (c == '+') {
                            result.add(l + r);
                        }
                    }
                }
            }
        }
        if (result.isEmpty()) {
            result.add(Integer.parseInt(expression));
        }
        memo.put(expression, result);
        return result;
    }
}

/*
所以關鍵是怎麼分支到剩兩個可以做運算 num1 operator num2, 左右分治可以做到
終止條件 base case 就是 沒operator 可以算, 是個數字

T: O(有多少分割方式) -> O(catalan number), 因為是像是組合數切割分治

"2*3-4*5"
->

1. "(2) *(3-4*5)"
       -> (3)-(4*5)
       -> (3-4)*(5)

2."(2 *3)(-4*5)"

3. "(2 *3-4)*(5)"
-> (2) *(3-4)
-> (2*3)-(4)


ex: 
"2-1-1"

   no opertaor, so add number to list[2]
  / 
"(2)-(1-1)"
       \
        return list[0]

        ->   list[2] - list[0] -> ans: 2

"(2-1)-(1)"
  /
  1

  -> list[1] - list[1] -> ans: 0

at last we can add memo to 

like 
1 + 1 + 1 + 1 + 1
那么按照算法逻辑，按照运算符进行分割，一定存在下面两种分割情况：

(1 + 1) + (1 + 1 + 1)
(1 + 1 + 1) + (1 + 1)

so 有重複
用 string 當 memo
*/
```