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.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> []
Solution 1: Use back Tracking, need to skip continuous zeros
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> res=new ArrayList<>();
if (num.length()==0) return res;
dfs(num,0,0,1,true,"",target,res);
return res;
}
private void dfs(String num, int d, long pre, long curr, boolean signPlus, String path, int target, List<String> res) {
int n=num.length();
for (int i=d+1; i<n; i++) {
if (num.charAt(d)=='0' && i>d+1) break;//if start with 0, can only be one digit
String s=num.substring(d,i);
long t=Long.valueOf(s);
dfs(num,i,pre,curr*t,signPlus,path+s+"*",target,res);//'*'
long nextPre=signPlus?pre+curr*t:pre-curr*t;
dfs(num,i,nextPre,1,true,path+s+"+",target,res);//'+'
dfs(num,i,nextPre,1,false,path+s+"-",target,res);//'-'
}
if (num.charAt(d)=='0' && n>d+1) return;//if start with 0, can only be one digit
String s=num.substring(d);
long t=Long.valueOf(s);
long total=signPlus?pre+curr*t:pre-curr*t;
if (total==target) res.add(path+s);
}
}
没有评论:
发表评论