字符串中的DFS

字符串的问题一般总是可以用DP来解决，但是也有很多用DFS解决的问题，这里汇总一下这样的题目，DFS的方法都差不多。
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 -> []

241.Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2
Input:"2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

[leetcode 282] Expression Add Operators

这种题目是最为常见的一道需要用DFS解决的题目，因为返回的是list，一般是DFS解。
这里主要是参考disscuss中排名第一的解法Java Standard Backtrace AC Solutoin, short and clear，其中提到三点：第一点是需要用长整形，第二点是需要考虑当第一个字符为0，就不需要继续添加字符，第三点是如果需要的运算符是*的话，需要记录前面一个数字，这里需要消除前面的操作，用前面的数字来乘当前的数字。就直接放代码了，形式比较固定：

public static List<String> addOperators(String num, int target) {
    List<String> list=new ArrayList<>();
    if(num==null||num.length()==0)return list;
    helper(list,"",num,target,0,0,0);
    return list;
}

private static void helper(List<String> list, String path, String s,int target, int index, long value, long pre) {
    if(index==s.length()){
       // System.out.println(path);
        if(value==target){
            list.add(path);
            System.out.println(path);
        }
    }else {
        for (int i=index;i<s.length();i++){
            if(i!=index&&s.charAt(index)=='0')break;//不能出现数字第一个为0的情况
            long cur=Long.parseLong(s.substring(index,i+1));
            if(index==0){
                helper(list,path+cur,s,target,i+1,cur,cur);//要记录出现*的时候，前一个数
            }else {
                helper(list,path+"+"+cur,s,target,i+1,value+cur,cur);
                helper(list,path+"-"+cur,s,target,i+1,value-cur,-cur);
                helper(list,path+"*"+cur,s,target,i+1,value-pre+pre*cur,pre*cur);
            }
        }
    }
}

在评论中也给出了字符串用StringBuilder的方法，让代码的运行速度快了不少，这里就不重复试验了。

[leetcode 241] Different Ways to Add Parentheses

这道题是用递归解的，我做不出来，但是还是记录一下，也是一种常见的题目，思路就是大问题转小问题，小问题又有不同的解，然后在将其组合起来。
见discuss中第一的解法A recursive Java solution (284 ms)

public List<Integer> diffWaysToCompute(String input) {
    List<Integer> ret = new LinkedList<Integer>();
    for (int i=0; i<input.length(); i++) {
        if (input.charAt(i) == '-' ||
            input.charAt(i) == '*' ||
            input.charAt(i) == '+' ) {
            String part1 = input.substring(0, i);
            String part2 = input.substring(i+1);
            List<Integer> part1Ret = diffWaysToCompute(part1);
            List<Integer> part2Ret = diffWaysToCompute(part2);
            for (Integer p1 :   part1Ret) {
                for (Integer p2 :   part2Ret) {
                    int c = 0;
                    switch (input.charAt(i)) {
                        case '+': c = p1+p2;
                            break;
                        case '-': c = p1-p2;
                            break;
                        case '*': c = p1*p2;
                            break;
                    }
                    ret.add(c);
                }
            }
        }
    }
    if (ret.size() == 0) {
        ret.add(Integer.valueOf(input));
    }
    return ret;
}