241. 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-(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]

Solution: Using divide and conquer, divide input to substring from (0, '+' / '-' / '$$$$') and ('+' / '-' / '$$$$' + 1, end)

1. start from the rightest operator of the input, divide the string into left and right
2. Continuously split substring into two until we reach to a single character (where the substring function will return null), then add the current single character into List and return.
3. Calculate the possible result with all elements in left list, to all elements in right list.

4. Improvements: A large number of substrings gets re-calculated many times, using hashmap to keep track.

   public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();
   
        for(int i = input.length()-1; i >= 0; i--){
            if (input.charAt(i) != '+' && input.charAt(i) != '-' && input.charAt(i) != '*'){
                continue;
            }else{
                String left = input.substring(0,i);
                String right = input.substring(i+1);
   
                List<Integer> left_res = diffWaysToCompute(left);
                List<Integer> right_res = diffWaysToCompute(right);
                for(int left_ele : left_res){
                    for(int right_ele : right_res){
                        int tmp = 0;
                        switch (input.charAt(i)){
                            case '+':
                                tmp = left_ele + right_ele;
                                break;
                            case '-':
                                tmp = left_ele - right_ele;
                                break;
                            case '*':
                                tmp = left_ele * right_ele;
                                break;
                        }
                        res.add(tmp);
                    }
                }
            }
        }
        if (res.size() == 0) {
            res.add(Integer.valueOf(input));
        }
        return res;
    }
   }
   

Reference: https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms/2