[Leetcode]282. Expression Add Operators

[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 -> []

拿到题目完全没思路啊，想不到除了暴力拆解加暴力加各种符号之外更好的例子。能想到的两点就是小细节：1. 字符串这东西这么长，分分钟overflow啊，2.0开头的各种字符串应该不算吧，0自己除外，3. 有乘号，乘号优先级高，要是从前往后算的话要处理一下运算顺序才行。

解决方法是：
1. 用long，
2. 0开头的，除了0自己，都忽略不算，
3. 为了解决乘号优先级，例如2+3*2，顺序算的话，我们先算出来2+3=5，看到乘号，我们用5-3=2，恢复到之前，再算3*2=6，然后加上之前的2，6+2=8。我们设置两个变量，一个是curSum 上一步的和，一个是diff， 上一步末尾的计算的数，如果是乘以出来的结果，就是那个结果, 有负号的话记得把负号也连带着用上。curSum = 2, diff = 3, curSum = 5; 运算到遇到了乘号，就用（curSum - diff ）+ diff*i。更新 curSum = 8， diff = diff * i, diff = 6. 如果2+3*2*2呢，继续用8 - 6 = 2，6*2 = 12， 12+2=14，我们的方法可以用，看着对对的。

以上难题都解决了呢，我们下一步看看如何实现。我一开始没思路的，很无耻的看了答案，答案上都说这个很明显用dfs，我就一脸懵逼了，哪里明显了？后来又一个良心答案说，题目让返回所有可能的解的组合，这就是让用dfs的意思。想来也颇有道理。我们要每次遍历到最后一个字符位置，确实是深度优先，然后每遍历一个字符，就要想在这一个字符和下一个字符之间要尝试所有的负号组合，如果想象成一个由数字组成的多叉树，就是一个tree的遍历，只不过每向下走一步，要尝试换符号。n方的复杂度，而且，没有更好的了。
做题的时候debug了一个bug一个小时，就是第一次初始化的时候，应该用y，我用了num，还有就是这个是从1，开始，到，length结束的。因为substring 闭开区间

AC Solution

public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<String>();
        helper(num, target, 0, 0, "", result);
        return result;
    }
    
    public void helper(String num, int target, long curSum, long diff, String tempRes, List<String> res){
        //System.out.println(curSum + ", " + num + ", " + tempRes);
        if(num.length() == 0 && curSum == target){
            res.add(tempRes);
            return;
        }
        for(int i = 1; i<= num.length(); ++i){ // This part begin from 1, and end for <= ,becasue it is for substring[i,j)
            String x = num.substring(0, i);
            String y = num.substring(i);
            if(x.length()>1 && x.charAt(0) =='0'){
                return;
            }
            long cur = Long.parseLong(x);
            if(tempRes.length()==0){
                // First time go into this
                helper(y, target, curSum + cur, cur, x, res);// 0 + whole number
            }
            else{
            helper(y, target, curSum + cur, cur, tempRes + "+" + cur, res);
            helper(y, target, curSum - cur, -cur, tempRes + "-" + cur, res);
            helper(y, target, (curSum - diff) + diff * cur, diff * cur, tempRes + "*" + cur, res);
            }  
        }
    }
}