Expression Add Operators

Divide and Conquer. add binary opeator, evaluate a string to a target number.

Way of Thinking

这个题对我来说非常tricky.主要是无法很清晰的分割问题。

Input: string. add + - * and make it result to target.

[n1] [n2] [n3] 
Case 1: we are going to add a "+". 
          prevRes = prevRes + curNum.
Case 2: we are going to add a "-". 
          prevRes = prevRes + curNum
Case 3: we are going to add a "*". 
    [n0] + [n1] * [n2] * [n3] * [cur]
   naive solution: 
   find out n1 * n2 * n3, calc res, say tRes.
         prevRes = (prevRes - tRes) + tRes * cur

Can we do better?

When add "", need to know previous number (group all together and make it a single number). we could carry this variable through recursion to avoid duplicate calculation.

One more step?

实际上，这个题的divide and conquer是把所有相同属性的state group然后区别对待，string only contains "+" and "-" 可以看成一个group，所有string only contains "*" 看成一个group.

无法定义出subproblem是什么，以及这个题subproblem之间的联系。

Another deinition.

Code Implementation DFS

public List<String> addOperators(String num, int target) {
    if (nums.length == 0) {
        return new ArrayList<String>();
    }
    List<String> res = new ArrayList<>();
    dfs(res,"",num,0,0, target);
    return res;
}
//use long instead of int, may be overflow
private void dfs(List<String> res, String path, String num, long prevNum, long curRes) {
    //base case
    if (curRes == target && num.length() == 0) {
        res.add(path);
        return;
    }
    //for any possible length of number.
    for(int i = 1; i <= num.length(); i++) {
        String curStr = num.substring(0,i);
        String rem = num.substring(i);
        //check valid number, '0xxx' is not valid 
        if (curStr.length() > 0 && curStr.charAt(0) == '0') {
            //directly return, no need to do further check.
            return;
        }
        long curNum = Long.valueOf(curStr);
        if (path.length() > 0) {
              //add "+"
              dfs(res,path + "+" + curStr, rem, curNum, curRes + curNum, target);
              //add '-'
              dfs(res,path + "-" + curStr, rem, -curNum, curRes - curNum, target);
              //add '*'
              dfs(res,path + "*" + curStr, rem, prevNum * curNum, curRes - prevNum + prevNum * curNum, target);
        } else {
            //don't add opeartor at first
            dfs(res,path + curStr, rem, curNum, curNum);
        }
    }
}