题目描述
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.
样例
Input = "123", target = 6
Output: ["1+2+3", "1*2*3"]
Input = "105", target = 5
Output: ["1*0*5", "10-5"]
算法1
(DFS 暴力枚举所有方案) $O(4^n)$
我们可以采用Leetcode Basic Calculator 2的方法,结合DFS枚举所有的方案。
注意这里以0打头的数字是不合法的,这是一种剪枝的方法。
时间复杂度
对于每一个位置,我们可以看到可以是四种情况+,-,*, ‘’。所以时间复杂度为$O(4^n)$.
参考文献
Java 代码
class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
if (num == null || num.length() == 0) return res;
helper(res, num, "", target, 0, 0, 0);
return res;
}
private void helper(List<String> res, String num, String unit_str, int target, long cur_sum, long last_elem, int index){
if (index == num.length()){
if (cur_sum == target){
res.add(unit_str);
}
return;
}
for (int i = index; i < num.length(); i ++){
if (i != index && num.charAt(index) == '0') break;
long val = Long.parseLong(num.substring(index, i+1));
if (unit_str.length() == 0){
helper(res, num, unit_str + val, target, cur_sum + val, val, i + 1);
}else{
//+
helper(res, num, unit_str + '+' + val, target, cur_sum + val, val, i + 1);
//-
helper(res, num, unit_str + '-' + val, target, cur_sum - val, -val, i + 1);
//*
helper(res, num, unit_str + '*' + val, target, (cur_sum - last_elem) + last_elem*val, last_elem*val, i + 1);
}
}//end for
}
}