yokostan / Leetcode-Solutions

Doing exercise on Leetcode. Carry on!
0 stars 3 forks source link

Leetcode #241 Different Ways to Add Parentheses #160

Open yokostan opened 5 years ago

yokostan commented 5 years ago

Divide and Conquer: It is very genius to divide the input into two parts each time we see an operator. At the very bottom (only one digit with no operator), we will add this digit(input) into res and return that result to upper levels. Note here that res are different (initialized each time and returned in different layers) so the only digits will not be returned to the final result if we have at least one operator(more levels). Very wise but basic D&C thinking.

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '-' || c == '+' || c == '*') {
                String a = input.substring(0, i);
                String b = input.substring(i + 1, input.length());
                List<Integer> al = diffWaysToCompute(a);
                List<Integer> bl = diffWaysToCompute(b);
                for (int x : al) {
                    for (int y : bl) {
                        if (c == '+') res.add(x + y);
                        else if (c == '-') res.add(x - y);
                        else res.add(x * y);
                    }
                }
            }
        }
        if (res.size() == 0) res.add(Integer.valueOf(input));
        return res;
    }
}