首页 > 代码库 > LeetCode-Different Ways to Add Parentheses
LeetCode-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: "2*3-4*5"
(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]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Solution:
public class Solution { HashSet<Character> operators; public List<Integer> diffWaysToCompute(String input) { operators = new HashSet<Character>(); operators.add(‘+‘); operators.add(‘-‘); operators.add(‘*‘); return diffWaysRecur(new StringBuilder().append(input),0,input.length()-1); } // Count different ways to compute sArr[start...end] public List<Integer> diffWaysRecur(StringBuilder sArr, int start, int end){ List<Integer> resList = new ArrayList<Integer>(); // find the first operator. int p1 = start; while (p1<=end && !operators.contains(sArr.charAt(p1))){ p1++; } if (p1>end){ // no operator, return the number. resList.add(Integer.parseInt(sArr.substring(start,end+1))); } while (p1<=end){ // Compute left substring and right substring List<Integer> leftRes = diffWaysRecur(sArr, start, p1-1); List<Integer> rightRes = diffWaysRecur(sArr, p1+1, end); for (int lVal : leftRes) for (int rVal : rightRes){ resList.add(compute(sArr.charAt(p1),lVal,rVal)); } // Looking for next operator. p1++; while (p1<=end && !operators.contains(sArr.charAt(p1))){ p1++; } } return resList; } public int compute(char oper, int v1, int v2){ if (oper == ‘+‘) return v1+v2; if (oper == ‘-‘) return v1-v2; if (oper == ‘*‘) return v1*v2; return 0; }}
LeetCode-Different Ways to Add Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。