282. Expression Add Operators

Description

image-20210816233523653

Solution

Use tricky DFS to solve it.

The most important trick: Because we need to give each expression that leads to the target, so we need to record current string. Then, for+ and -, in fact we just need to record the exep value in previous expression. But to treat * rightly, we need record one more variable – lastValue to calculate the expression rightly.

So if we have, for example 1 2 3 4 5 6 7 8

1
1 + 2 * 3 DFS(45678)

​ ↑

To treat this 2 * 3 correctly, we need first record 1 + 2= 3, then use 3 - 2 + 2 * 3 to get the right answer.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    vector<string> res;
    typedef long long LL;
public:
    vector<string> addOperators(string num, int target) {
        dfs(num, (LL)target, "", 0, 0, 0);
        return res;
    }
    
    void dfs(string& num, LL target, string prevStr, int curPos, LL curVal, LL lastVal){
        if(num.size() == curPos){
            if(curVal == target)
                res.push_back(prevStr);
            return;
        }
        
        for(int i = curPos; i < num.size(); i++){
            string curStr = num.substr(curPos, i - curPos+1);
            // cout << curStr <<endl;
            LL val = stoll(curStr);
            
            if(curStr.size() > 1 && curStr[0] =='0') continue;
            if(curPos==0){
                dfs(num, target, curStr, i+1, val, val);
            }else{
                dfs(num, target, prevStr + "+" + curStr, i+1, curVal + val, val);
                dfs(num, target, prevStr + "-" + curStr, i+1, curVal - val, -val);
                dfs(num, target, prevStr + "*" + curStr, i+1, curVal - lastVal + lastVal * val, lastVal * val);
            }
        }
    }
};

image-20210816234051340