LeetCode: Different Ways to Add Parentheses 给公式加括号

忘是亡心i 2021-06-24 16:10 312阅读 0赞

**试题：**  
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  
**代码：**  
我们先添加最外层的括号，添加完后，递归的对括号内的内容进行添加。  
在返回时将所有可能的取值都保存着。

class Solution {
        public List<Integer> diffWaysToCompute(String input) {
            List<Integer> way = new ArrayList<>();
            for(int i=0; i<input.length(); i++){
                char c = input.charAt(i);
                if(c=='+' || c=='-' ||c=='*'){
                    List<Integer> left = diffWaysToCompute(input.substring(0,i));
                    List<Integer> right = diffWaysToCompute(input.substring(i+1));
                    for(int l:left){
                        for(int r:right){
                            switch(c){
                                case '+':
                                    way.add(l+r);
                                    break;
                                case '-':
                                    way.add(l-r);
                                    break;
                                case '*':
                                    way.add(l*r);
                                    break;
                            }
                        }
                    }
                }
            }
            if(way.size()==0){
                way.add(Integer.valueOf(input));
            }
            return way;
        }
    }