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 .Example 1:Input: “2-1-1"Output: [0, 2]Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2Example 2:Input: “23-45"Output: [-34, -14, -10, -10, 10]Explanation: (2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10难度：medium题目：给定一包含数字和操作符的字符串，计算并返回其所有数字与操作符组合的结果。有效的操作符为+,-,思路：类似unique binary tree, generate parentheses. 卡特兰数。 Runtime: 2 ms, faster than 84.52% of Java online submissions for Different Ways to Add Parentheses.Memory Usage: 38.6 MB, less than 18.35% of Java online submissions for Different Ways to Add Parentheses.class Solution { public List<Integer> diffWaysToCompute(String input) { return diffWaysToCompute(input, 0, input.length()); } private List<Integer> diffWaysToCompute(String str, int start, int end) { if (!hasOperator(str, start, end)) { List<Integer> result = new ArrayList<>(); result.add(Integer.parseInt(str.substring(start, end))); return result; } List<Integer> root = new ArrayList<>(); for (int i = start; i < end; i++) { char c = str.charAt(i); if (’+’ == c || ‘-’ == c || ‘’ == c) { List<Integer> left = diffWaysToCompute(str, start, i); List<Integer> right = diffWaysToCompute(str, i + 1, end); for (Integer l: left) { for (Integer r : right) { if (’+’ == c) { root.add(l + r); } else if (’-’ == c) { root.add(l - r); } else if (’’ == c) { root.add(l * r); } } } } } return root; } private boolean hasOperator(String s, int start, int end) { for (int i = start; i < end; i++) { char c = s.charAt(i); if (’+’ == c || ‘-’ == c || ‘*’ == c) { return true; } } return false; }}