LeetCode: Different Ways to Add Parentheses 给公式加括号 忘是亡心i 2021-06-24 16:10 259阅读 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; } }
还没有评论,来说两句吧...