2015年11月5日星期四

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.
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);  
   }  
 }  

没有评论:

发表评论