Google
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