# 282. Expression Add Operators

![](/files/wJfJBnAabbprhXHfqeHd)

![](/files/7v2IIZaGyvoIg6QjE9RI)

### 記得三巨頭 String preStr, long preVal, long lastVal

dfs for style

```
Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]

針對 1 2 3 中間去加算數符號



String curStr = num.substring(0, i+1); 
窮舉所有數字的可能, 去搭
curStr:1
nextStr:23 // String nextStr = num.substring(i+1);, 剩下的

curStr:2
nextStr:3
curStr:3
nextStr:
curStr:3
nextStr:
curStr:3
nextStr:
curStr:23
nextStr:
curStr:12
nextStr:3
curStr:3
nextStr:
curStr:123
nextStr:


for 1
curStr = 1
nextStr = 23
so parse 1 first, save to preStr, preVal

所以 +, - 很直觀就是
preStr + "+" + curStr, preVal+curVal
preStr + "-" + curStr, preVal-curVal

但還要多一個 lastVal, why? for *

## *號

這裡就要利用之前歸納出的結果

1+23+4*DFS...

preVal 包含了 1+23+4 = 28, 但其實 4不應該計算進去, 所以需要紀錄 lastVal


preVal 要剪掉 4(lastVal), 然後 lastVal 在跟之後的乘, 
⇒  dfs preVal = preVal- lastVal + lastVal * curVal

dfs lastVal ＝ lastVal * curVal


注意 curStr 的字是 0開頭長度大於1的, 不處理
// 05 這種字不處理
            if (curStr.charAt(0) == '0' && curStr.length() > 1) {
                continue;
            }
```

```
T: 4 dfs, 4 choice, 4*4*4..., O(4^n), and substing operationis O(n) so O(n*4^n)
S: O(n), dfs stack space
```

```java
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        dfs(res, num, (long)target, "", 0, 0);
        return res;
    }
    private void dfs(List<String> res, String num, long target, 
        String preStr, long preVal, long lastVal) {
        
        // nextStr 用盡時, 且 preVal(pre result) == target
        if (num.length() == 0 && preVal == target) {
            res.add(preStr);
            return;
        }
        
        for (int i = 0; i < num.length(); i++) {
            String curStr = num.substring(0, i+1);
            // in next dfs, use remain string
            String nextStr = num.substring(i+1); 
            
            // for ["1*0+5","1*05","10-5"] this test case, we should handle "1*05" this case, it's illegal
            // 05 這種字不處理
            if (curStr.charAt(0) == '0' && curStr.length() > 1) {
                continue;
            }
            
            long curVal = Long.parseLong(curStr);
            if ("".equals(preStr)) {
                dfs(res, nextStr, target, curStr, curVal, curVal);
            } else {
                dfs(res, nextStr, target, preStr + "+" + curStr, preVal+curVal, curVal);
                dfs(res, nextStr, target, preStr + "-" + curStr, preVal-curVal, -curVal);
                dfs(res, nextStr, target, preStr + "*" + curStr, preVal-lastVal + lastVal*curVal, lastVal*curVal);
            }
        }
    }
}

/*
T: 4 dfs, 4 choice, 4*4*4..., O(4^n), and substing operationis O(n) so O(n*4^n)
S: O(n), dfs stack space

1. 
for i = curPos+1
substr(curPos, i - curPos)

3 DFS for +, -, *




2. 
  1    +-*   2      + dfs(345)
preStr      currVal
preVal

but * is spaecail, due to mutiply priority

1 + 2 * dfs(345)

1 + 2 cant cal first, so need keep last part of 1 + 2 => 2

dfs() preval = 
preVal - lastVal + lastVal*currVal

long preVal, long lastVal => avoid after * to overflow number

3. 
terminal condition
curPos == num.length() && preStr == target

4. for ["1*0+5","1*05","10-5"] this test case, we should handle "1*05" this case, it's illegal

*/j
```


---

# 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/tips/282.-expression-add-operators.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.