# 241. Different Ways to Add Parentheses

````java
```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)

```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) {
        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
    }
}


*/
```

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

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

        for (int i = 0; i &#x3C; expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '-' || c == '*' || c == '+') {
                List&#x3C;Integer> left = diffWaysToCompute(expression.substring(0, i));
                List&#x3C;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 可以算, 是個數字

<strong>T: O(有多少分割方式) -> O(catalan number), 因為是像是組合數切割分治
</strong>
"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
*/
```
</code></pre>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/241.-different-ways-to-add-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.