282 Expression Add Operators

282. Expression Add Operators​
1. Question
Given a string that contains only digits0-9and a target value, return all possibilities to addbinaryoperators (not unary)+,-, or*between the digits so they evaluate to the target value.
Examples:
1
"123", 6 -> ["1+2+3", "1*2*3"] 
2
"232", 8 -> ["2*3+2", "2+3*2"]
3
"105", 5 -> ["1*0+5","10-5"]
4
"00", 0 -> ["0+0", "0-0", "0*0"]
5
"3456237490", 9191 -> []
Copied!
2. Implementation
(1) Backtracking
思路: 这道题主要就是用Backtracking枚举所有可能的结果，但要注意的edge cases和要处理的问题有:
1.以0开头的非个位数,比如01, 012,这些都是invalid的遇到时我们要直接跳过
2.乘法的优先级会高于加减法，比如2+3*4这种情况，我们按顺序2 + 3的话会得到5，但遇到乘号是，我们要减去3，然后用3乘以4得到12再加回2才等到正确的结果14，所以我们在backtracking的过程中，我们要维护prevNum这个变量记录之前的数，以及curRes记录当前的结果，如果遇到乘号时，curRes先减去prevNum,然后再加上prevNum * curNum。
1
class Solution {
2
    public List<String> addOperators(String num, int target) {
3
        List<String> res = new ArrayList();
4
        StringBuilder expression = new StringBuilder();
5
​
6
        getExpressions(0, num, 0, 0, target, expression, res);
7
        return res;
8
    }
9
​
10
    public void getExpressions(int startIndex, String num, long prevNum, long curRes, int target, StringBuilder expression, List<String> res) {
11
        if (startIndex == num.length() && curRes == target) {
12
            res.add(expression.toString());
13
            return;
14
        }
15
​
16
        int len = expression.length();
17
​
18
        for (int i = startIndex; i < num.length(); i++) {
19
            if (num.charAt(startIndex) == '0' && i != startIndex) break;
20
​
21
            String curStr = num.substring(startIndex, i + 1);
22
            Long curNum = Long.parseLong(curStr);
23
​
24
            if (len != 0) {
25
                getExpressions(i + 1, num, prevNum * curNum, (curRes - prevNum) + (prevNum * curNum), target, expression.append("*").append(curNum), res);
26
                expression.setLength(len);
27
                getExpressions(i + 1, num, curNum, curRes + curNum, target, expression.append("+").append(curNum), res);
28
                expression.setLength(len);
29
                getExpressions(i + 1, num, -curNum, curRes - curNum, target, expression.append("-").append(curNum), res);
30
                expression.setLength(len);
31
            }
32
            else {
33
                getExpressions(i + 1, num, curNum, curNum, target, expression.append(curStr), res);
34
                expression.setLength(len);
35
            }
36
        }
37
    }
38
}
Copied!
3. Time & Space Complexity
时间复杂度O(n * 4^(n - 1)), n为num的长度，在num之间有n - 1个slot，对于每个slot我们有4种选择，不插入任何operator，插入3种(+, -, *)operators，对于遍历num的每个位置，我们都要O(4^(n - 1))的时间，总共有n步，所以需要O(n * 4^(n - 1)), 空间复杂度O(n), 递归的深度为n

308 Range Sum Query 2D - Mutable

616 Add Bold Tag in String

Last modified 2yr ago

Copy link

Contents

282. Expression Add Operators

1. Question

2. Implementation

3. Time & Space Complexity

282. Expression Add Operators​

1. Question

2. Implementation

3. Time & Space Complexity

282. Expression Add Operators