package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/different-ways-to-add-parentheses/
 */
public class Problem241 {
    public List<Integer> diffWaysToCompute(String input) {
        if (input.length() == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(Integer.valueOf(input));
            return list;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i < input.length(); i += 2) {
            if (input.charAt(i) == '+' || input.charAt(i) == '-'
                || input.charAt(i) == '*') {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i+1, input.length()));
                for (int l : left) {
                    for (int r : right) {
                        if (input.charAt(i) == '+') {
                            result.add(l + r);
                        } else if (input.charAt(i) == '-') {
                            result.add(l - r);
                        } else if (input.charAt(i) == '*') {
                            result.add(l * r);
                        }
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Problem241 prob = new Problem241();
        for (int i : prob.diffWaysToCompute("2-1-1")) {
            System.out.println(i);
        }
        System.out.println("----------------------------");
        for (int i : prob.diffWaysToCompute("2*3-4*5")) {
            System.out.println(i);
        }
        System.out.println("----------------------------");
        for (int i : prob.diffWaysToCompute("11")) {
            System.out.println(i);
        }
    }
}

@@ -241,27 +241,76 @@
 if (
+!
 input.
-length() == 1
+contains(%22+%22) && !input.contains(%22-%22) && !input.contains(%22*%22)
 ) %7B%0A
@@ -513,17 +513,17 @@
 int i = 
-1
+0
 ; i %3C in
@@ -541,13 +541,10 @@
 ); i
- += 2
+++
 ) %7B%0A
@@ -1345,525 +1345,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem241 prob = new Problem241();%0A        for (int i : prob.diffWaysToCompute(%222-1-1%22)) %7B%0A            System.out.println(i);%0A        %7D%0A        System.out.println(%22----------------------------%22);%0A        for (int i : prob.diffWaysToCompute(%222*3-4*5%22)) %7B%0A            System.out.println(i);%0A        %7D%0A        System.out.println(%22----------------------------%22);%0A        for (int i : prob.diffWaysToCompute(%2211%22)) %7B%0A            System.out.println(i);%0A        %7D%0A    %7D
 %0A%7D%0A

Solve problem 241