正文
[leetcode]282. Expression Add Operators 表达式添加运算符
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
Given a string that contains only digits
0-9
and a target value, return all possibilities to add binary operators (not unary)
+
,
-
, or
*
between the digits so they evaluate to the target value.
Example 1:
Input:num ="123", target = 6
Output: ["1+2+3", "1*2*3"]
Example 2:
Input:num ="232", target = 8
Output: ["2*3+2", "2+3*2"]
Example 3:
Input:num ="105", target = 5
Output: ["1*0+5","10-5"]
Example 4:
Input:num ="00", target = 0
Output: ["0+0", "0-0", "0*0"]
Example 5:
Input:num ="3456237490", target = 9191
Output: []
题目
给定一个数字串S和一个值target，允许你在S中间添加加减乘符号，使得表达式结果为target，求所有添法。
思路
dfs + pruning（适当剪枝）
代码
class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
dfs(num, 0, 0, 0, "", res, target);
return res;
}
private void dfs(String num, int index, long sum, long last, String s, List<String> res, int target) {
if(index == num.length()) {
if(sum == target) {
res.add(s);
}
}
for(int i = index + 1; i <= num.length(); i++) {
String temp = num.substring(index, i);
if(temp.length() > 1 && temp.charAt(0) == '0') {
continue;
}
long n = Long.valueOf(temp);
if(index == 0) {
dfs(num, i, sum + n, n, s + n, res, target);
continue;
}
dfs(num, i, sum + n, n, s + "+" + n, res, target);
dfs(num, i, sum - n, -n, s + "-" + n, res, target);
dfs(num, i, (sum-last) + last * n, last * n, s + "*" + n, res, target);
}
}
}
