Expression Add Operators

• DFS + Backtracking的思路

• 第一步, 取1到n个数为开始

• DFS的时候每一步可以选取1到k个数为下一个元素

  • 加法: curval = curval + preval, preval 此时为Long.parseLong (numstr)

  • 减法: curval = curval-preval, preval 此时为-Long.parseLong(numstr)

  • 乘法: curval首先要抹去之前的preval, curval-=preval, 之后curval加上 preval*当前的元素, preval=preval*当前的元素

• 注意: 要选用Long, 毕竟string有时候还是挺大的, 可以和面试官讨论range

• 注意: 当numstr长度大于1时, 首字符不能为0, 如"05"

• public class Solution {
      public List<String> addOperators(String num, int target) {
          ArrayList<String> ans = new ArrayList<String>();
          dfs(num, target, ans, 0L, 0L, "");
          return ans;
      }
  
      public void dfs(String num, int target, ArrayList<String> ans,Long cur, Long diff, String curStr){
          if(num.length()==0){
              if(cur==target){
                  ans.add(curStr);
              }
              return;
          }
          if(curStr.length()>0){//key point
              for(int i=0;i<num.length();i++){
                  String numStr = num.substring(0, i+1);
                  String next = num.substring(i+1);
                  if(numStr.length()>1 && numStr.charAt(0)=='0' ) return;
                  dfs(next, target, ans, cur + Long.parseLong(numStr), Long.parseLong(numStr), curStr + "+" +numStr); //key point: Long.parseLong()
                  dfs(next, target, ans, cur-Long.parseLong(numStr), -Long.parseLong(numStr), curStr + "-" + numStr);
                  dfs(next, target, ans, (cur-diff)+diff*Long.parseLong(numStr), diff*Long.parseLong(numStr), curStr + "*" + numStr);
              }
          }else{
              for(int i=0;i<num.length();i++){
                  String numStr = num.substring(0, i+1);
                  String next = num.substring(i+1);
                  if(numStr.length()>1 && numStr.charAt(0)=='0' ) return; //key point
                  dfs(next, target, ans,  Long.parseLong(numStr), Long.parseLong(numStr), numStr);
                  /*
                  dfs(next, target, ans, cur-Long.parseLong(numStr), -Long.parseLong(numStr), "-" + numStr);
                  */
              }
          }
      }
  }
  

short and concise solution

public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> rst = new ArrayList<String>();
        if(num == null || num.length() == 0) return rst;
        helper(rst, "", num, target, 0, 0, 0);
        return rst;
    }
    public void helper(List<String> rst, String path, String num, int target, int pos, long eval, long multed){
        if(pos == num.length()){
            if(target == eval)
                rst.add(path);
            return;
        }
        for(int i = pos; i < num.length(); i++){
            if(i != pos && num.charAt(pos) == '0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            if(pos == 0){
                helper(rst, path + cur, num, target, i + 1, cur, cur);
            }
            else{
                helper(rst, path + "+" + cur, num, target, i + 1, eval + cur , cur);

                helper(rst, path + "-" + cur, num, target, i + 1, eval -cur, -cur);

                helper(rst, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );
            }
        }
    }
}