241. Different Ways to Add Parentheses

Link

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"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(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

Solution 這題觀察到可以將問題切成若干子問題。然後透過子問題的組合求出所有可能性。 所以用遞迴。之所以不用DP的原因是因為子問題間並無關聯性，也不會有重複計算的問題。

  public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i < input.length(); i++){
            char c = input.charAt(i);
            if(c == '-' || c == '+' || c == '*'){
                String subString1 = input.substring(0, i);
                String subString2 = input.substring(i+1);
                List<Integer> ret1 = diffWaysToCompute(subString1);
                List<Integer> ret2 = diffWaysToCompute(subString2);
                
                for(Integer a : ret1){
                    for(Integer b : ret2){
                        if(c == '-'){
                            ret.add(a-b);
                        }
                        else if(c == '+'){
                            ret.add(a+b);
                        }
                        else if(c == '*'){
                            ret.add(a*b);
                        }   
                    }
                }
            }
        }
        //Avoid only one integer in the input
        if(ret.size() == 0){
            ret.add(Integer.parseInt(input));
        }
        
        
        return ret;
    }