LeetCode300/282. Expression Add Operators.java at master · Dukecat0613/LeetCode300 · GitHub

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
33
34
35
36
37
38
39
public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        for (int i = 1; i <= num.length(); i++) {
            String tmp = num.substring(0, i);
            if (tmp.length() > 1 && tmp.startsWith("0")) continue;
            dfs(res, num, 0, i, target, tmp, '*', Long.valueOf(tmp));
        }
        return res;
    }
    public void dfs(List<String> res, String num, long left, int i, int target, String cur, char op, long val) {
        if (val < Integer.MAX_VALUE && (int)val == target && i == num.length()) {
            res.add(cur);
            return;
        }
        if (i >= num.length()) {
            return;
        }

        for (int j = i + 1; j <= num.length(); j++) {
            String tmp = num.substring(i, j);
            if (tmp.length() > 1 && tmp.startsWith("0")) continue;
            long curVal = long.valueOf(tmp);
            // +
            dfs(res, num, curVal, j, target, cur + "+" + tmp, '+', val + curVal);
            // -
            dfs(res, num, curVal, j, target, cur + "-" + tmp, '-', val - curVal);
            // *
            if (op == '+') {
                dfs(res, num, left * curVal, j, target, cur + "*" + tmp, '+', val - left + left * curVal);
            } else if (op == '-') {
                dfs(res, num, left * curVal, j, target, cur + "*" + tmp, '-', val + left - left * curVal);
            } else {
                dfs(res, num, left * curVal, j, target, cur + "*" + tmp, '*', val * curVal);
            }
        }

    }
}