241. Different Ways to Add Parentheses

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: "23-45" (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10 Output: [-34, -14, -10, -10, 10]

Credits:Special thanks to @mithmatt for adding this problem and creating all test cases.

Solution

public class Solution {
  public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();

        if (input == null || input.length() == 0) {
            return result;
        }

        for (int i = 1; i < input.length()-1; i++) {
            char currentChar = input.charAt(i);
            if (currentChar != '*' && currentChar != '+' && currentChar != '-') {
                continue;
            }

            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1, input.length()));


            for (Integer l : left) {
                for (Integer r : right) {
                    switch (currentChar) {
                        case '*':
                            result.add(l * r);
                            break;

                        case '+':
                            result.add(l + r);
                            break;

                        case '-':
                            result.add(l - r);
                            break;
                    }

                }
            }
        }

        if (result.size() == 0) {
            result.add(Integer.valueOf(input));
        }

        return result;
    }
}