Different Ways to Add Parentheses
- medium
- tag: recursion, DP
- similar: unique BST, triangle
- 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 : Input: "23-45"
(2(3-(45))) = -34 ((23)-(45)) = -14 ((2(3-4))5) = -10 (2((3-4)5)) = -10 (((23)-4)5) = 10
- Output: [-34, -14, -10, -10, 10]
思路
- 我已开始的想法是想着用permutation/subset的模版. 但是好象不对.
- 其实题目已经提示了: tag: Divide and Conquer. 这很明显是通过operator来分割左右expression, 然后左右expression递归得到的list
来分别组合left/right得到当前expression的解并放入到result list中.
idea 1:
- 直接使用递归, 通过operator作为分割点, 对左右expr进行recursion得到的list来for loop得到当前expression的解并放入到结果list.
- 需要注意边界条件.
- 代码如下:
public List<Integer> diffWaysToComputeStefan(String input) {
List<Integer> output = new ArrayList<>();
for (int i = 0; i < input.length(); ++i) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
for (int a : diffWaysToComputeStefan(input.substring(0, i))) {
for (int b : diffWaysToComputeStefan(input.substring(i + 1))) {
output.add(c == '+' ? a + b : c == '-' ? a - b : a * b);
// 这里使用tenary operator ? 简化了3次if/else. 学习的stefan大神的答案
}
}
}
}
if (output.size() == 0) {
output.add(Integer.parseInt(input));
}
return output;
}
idea 2: 使用memorization的recursion
- 很明显: 每一个表达式很有可能在左右都遇到, 如果左边的同一个表达式已经计算过了, 那么右边出现的同样表示就直接返回结果了. 即memorization的recursion写法. 可以加速一点.
- 代码如下:
public List<Integer> diffWaysToCompute(String input) {
Map<String, List<Integer>> cache = new HashMap<>();
return helper(input, cache);
}
private List<Integer> helper(String s, Map<String, List<Integer>> cache) {
if (cache.get(s) != null) {
return cache.get(s); // 这里就发现为什么map定义成List而不是Integer了: 因为可以直接return了.
}
boolean expr = false;
List<Integer> result = new ArrayList<>();
for (int i = 0; i < s.length(); ++i) {
if ("+-*".indexOf(s.charAt(i)) != -1) {
for (int left : helper(s.substring(0, i), cache)) {
for (int right : helper(s.substring(i + 1), cache)) {
result.add(s.charAt(i) == '+' ? left + right
: s.charAt(i) == '-' ? left - right : left * right);
}
}
expr = true;
}
}
if (!expr) result.add(Integer.parseInt(s));
cache.put(s, result);
return result;
}
但是我提交了之后发现比SylvanasWindrunner的实现要慢很多. 这是为什么呢?
- 因为我用的recursion!
不过只要写好了recursion with memorization, 就离DP不远了.
idea 3: DP
- 既然上面已经写出了recursion with memorization了. 那么DP怎么写呢?
- 定义state: 即dp[i][j], 表示[i...j]之间所能得到的所有可能值.
- 这种分段型的dp都是外层loop循环段的长度, 然后i,j分别表示起点,终点. 这里的细节要熟练.
- 代码如下:
public List<Integer> diffWaysToComputeBest(String input) {
List<Integer> result = new ArrayList<>();
if (input == null || input.length() == 0) return result;
List<String> ops = new ArrayList<>();
// 先是将所有数字和'+-*'放到list里
for (int i = 0; i < input.length(); ++i) {
int j = i;
while (j < input.length() && Character.isDigit(input.charAt(j))) {
j++;
}
ops.add(input.substring(i, j));
if (j != input.length()) ops.add(input.substring(j, j + 1));
i = j;
}
int N = (ops.size() + 1) >> 1;
List<Integer>[][] dp = (ArrayList<Integer>[][])new ArrayList[N][N];
// 按照state的长度打表
for (int len = 0; len < N; ++len) {
if (len == 0) {
for (int i = 0; i < N; ++i) {
dp[i][i] = new ArrayList<>();
dp[i][i].add(Integer.valueOf(ops.get(i * 2)));
}
continue; // 计算完len = 0的之后就update len, 所以要continue
}
for (int i = 0; i < N - len; ++i) {
dp[i][i + len] = new ArrayList<>();
for (int j = i; j < i + len; ++j) {
// 由于是按照state的长度来loop, 所以此时已经计算完所有len = 0到len-1的了!
List<Integer> left = dp[i][j], right = dp[j + 1][i + len];
for (int l : left) {
for (int r : right) {
String op = ops.get(j * 2 + 1);
dp[i][i + len].add(op.equals("+") ? l + r : op.equals("-") ? l - r : l * r);
}
}
}
}
}
return dp[0][N - 1];
}