02 Jan 2017

Recursion to divide and conquer II

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

This example will show you how to use recursion method solve problem, then lead to two Divide and Conquer solution.

Different Ways to Add Parentheses

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

### Video explanation

Divide and Conquer

Recursion method is all about how many option you have in each step, if you have N option, then divide it into N sub problem. Here the number of option is number of operator we have. Instead of evaluate that option first, we will evaluate that option last, this is much better to handle duplicate case and multiple sub-string.

public class DifferentWays {
    public List<Integer> diffWaysToCompute(String input) {
        if (input.isEmpty())
            return null;
        return diffWaysToCompute(input, 0, input.length()-1);
    }
    boolean isOprator(char ch) {
        return ch == '+' || ch == '-' || ch == '*';
    }
    private static int cal(int left, int right, char operator) {
        if (operator == '+') {
            return left + right;
        } else if (operator == '-') {
            return left - right;
        } else {
            return left * right;
        }
    }
    public List<Integer> diffWaysToCompute(String input, int L, int R) {
        List<Integer> all = new ArrayList<Integer>();
        List<Integer> left;
        List<Integer> right;
        for (int i = L; i <= R; i++) {
            if (isOprator(input.charAt(i))) {
                left = diffWaysToCompute(input, L, i-1);
                right = diffWaysToCompute(input, i+1, R);
                for (int l : left) {
                    for (int r : right) {
                        all.add(cal(l, r, input.charAt(i)));
                    }
                }
            }
        }
        if (all.size() == 0) {
            all.add(Integer.parseInt(input.substring(L, R+1)));
        }
        return all;
    }
}