241. Different Ways to Add Parentheses - jiejackyzhang/leetcode-note GitHub Wiki
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]
解题思路为divide-and-conquer。与由1,...,n生成BST树的题目类似。
没找到一个operator，都可以把string分成左右两部分，然后对这个sub problem采取同样的做法。 采用hash map可以避免对相同的部分重复计算。
public class Solution {
Map<String, List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if(c == '+' || c == '-' || c == '*') {
String s1 = input.substring(0, i);
String s2 = input.substring(i+1);
List<Integer> l1 = map.getOrDefault(s1, diffWaysToCompute(s1));
List<Integer> l2 = map.getOrDefault(s2, diffWaysToCompute(s2));
for(Integer i1 : l1) {
for(Integer i2 : l2) {
int r = 0;
switch(c) {
case '+':
r = i1 + i2;
break;
case '-':
r = i1 - i2;
break;
case '*':
r = i1 * i2;
break;
}
res.add(r);
}
}
}
}
if(res.size() == 0) {
res.add(Integer.valueOf(input));
}
map.put(input, res);
return res;
}
}