leetcode 241:Different Ways to Add Parentheses

本文主要是介绍leetcode 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 *.

题目分析：看到这个题，第一反应竟然是相邻数字跟符号的随机组合，然后计算结果后与剩下的再随机组合，这样会导致重复计算，所以结果会重，因为当时想的结果是set，之后想，可以以符号作为区分，符号两边递归计算，并且得到全排列的结果，如果没有符号，直接得到string转num.有点类似于二叉树的求解。

具体代码如下：

public List<Integer> diffWaysToCompute(String input) {int len=input.length();List<Integer> res = new ArrayList<Integer>();if(len<1) return res;for(int i=0;i<len;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(Integer leftnum:left){for(Integer rightnum:right){switch(c){case '+':res.add(leftnum+rightnum); break;case '-':res.add(leftnum-rightnum); break;case '*':res.add(leftnum*rightnum); break;default: break;}}}}}//没有符号分割，直接返回结果if(res.size()==0)res.add(Integer.parseInt(input));return res;}

这篇关于leetcode 241:Different Ways to Add Parentheses的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---