282. Expression Add Operators

記得三巨頭 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

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