22 Jan 2017

Recursion tree and recursion tree traversal III

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2017/01/22/exp-add-op.html

This example will show you how to use recursion tree to solve problem. the example is leetcode Expression Add Operators. Start from Recursion tree and recursion tree traversal I and Recursion tree and recursion tree traversal II If you feel this one is hard for you.

Expression Add Operators

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

Video explanation

DFS brute force

If you studied my previous video, you should be able to draw the recursion tree easily, then get this 1st solution easily.

class Node {
    long v;
    String s;
    Node(long v, String s) { this.v = v; this.s = s; }
}

public List<String> addOperators(String num, int target) {
    return dfs(num, target);
}
private List<String> dfs(String num, int target) {
    List<Node> all = dfs(num, 0, target);
    List<String> str = new ArrayList<String>();
    // for (Node n : all)
    //    System.out.println(n.s + " = " + Long.toString(n.v));
    for (Node n: all) {
        if (n.v == target)
            str.add(n.s);
    }
    return str;
}
private List<Node> dfs(String num, int pos, int target) {
    List<Node> all = new ArrayList<Node>();
    if (pos == num.length())
        return all;
    for (int i = pos; i < num.length(); i++) {
        String s = num.substring(pos, i+1);
        long v = Long.parseLong(s);
        List<Node> opt1 = dfs(num, i+1, target);
        for (Node n : opt1) {
            all.add(new Node(v+n.v, s + "+" + n.s));
            all.add(new Node(v-n.v, s + "-" + n.s));
            all.add(new Node(v*n.v, s + "*" + n.s));
        }
        if (opt1.isEmpty()) 
            all.add(new Node(v, s));
        if (num.charAt(pos) == '0')
            break;
    }
    return all;
}

At first I thought this is good, but the problem is multiply, it failed on OJ, e.g. for input “232”, with target=8. the output is: [2+3 * 2], it missed [2 * 3+2]. the value compute by this solution is 2 * (3+2)=10, not 8.

Now we can focus on how to deal with order of operations, for example, we need covert 2 * (3+2) to 2 * 3+2. when the sub-problem “32” return, the sum(recorded in node.v) is 5(3+2). we need convert it to 2 * (5-X) + X. what is the value of X? it is 2, the value of previous sub-proble.

It works for subtraction as well, e.g. [2 * 3-2] will get result 1[2 * (3-2)], but we need turn it to 4[(2 * 3)-2]. current sum is 1(3-2), previous sum is -2. 2 * (1-(-2))+(-2) = 4

To make the code neat, you need to really understand what happens on stack during recursive function call. As practice, you can finish the solution by add another integer to the auxiliary structure node. like this:

class Node {
    long sum;
    long preSum;
    String s;
    Node(long sum, long preSum, String s) { 
        this.sum = sum; 
        this.preSum = preSum; 
        this.s = s;
    }
}

preSum is 0 at leaf node, after you finish it, then try to eliminate the auxiliary structure. Here is final code.

public List<String> addOperators(String num, int target) {
    List<String> all = new ArrayList<String>();
    dfs(num, 0, target, 0, 0, "", all);
    return all;
}
private void dfs(String num, int pos, int target, long curSum,
                long preSum, String exp, List<String> all) {
    if (pos == num.length() && curSum == target) {
        all.add(exp);
        return;
    }
    for (int i = pos; i < num.length(); i++) {
        String s = num.substring(pos, i+1);
        long v = Long.parseLong(s);
        if (exp.isEmpty()) {
            dfs(num, i+1, target, curSum+v, curSum, s, all);
        } else {
            dfs(num, i+1, target, curSum+v, curSum, exp+"+"+s, all);
            dfs(num, i+1, target, curSum-v, curSum, exp+"-"+s, all);
            dfs(num, i+1, target, (curSum-preSum)*v+preSum, preSum, exp+"*"+s, all);
        }
        if (num.charAt(pos) == '0')
            return;
    }
}