241. Different Ways to Add Parentheses
https://leetcode.com/problems/different-ways-to-add-parentheses/
自己做的感觉不太好，听了花花酱的讲解后写了一版Java的，时间和内存可以达到都是 100%。
这道题目的关键在于：
- 递归的方式是按照操作符拆成左右两边表达式，左边的 List 和 右边的 List 进行笛卡尔积处理（以该操作符处理）。
- 递归的终止条件是字符串本身是个数值，没有操作符，那结果就将其放入到一个新 List 中返回。
- 重复计算：以用例
2*3-4*5来说，计算方式可以有(2*(3-(4*5)))以及((2*3)-(4*5))，这里面的4*5会重复计算到，所有可以使用 map 记住字符串的计算结果。
试了下不带缓存的版本：Runtime: 2 ms, faster than 75.34%；Memory Usage: 38.6 MB, less than 65.42%，效果依然是不错的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| public List<Integer> diffWaysToCompute(String input) {
if (input == null || input.length() == 0) {
return new ArrayList<>();
}
return handle(input, new HashMap<>());
}
private List<Integer> handle(String str, Map<String, List<Integer>> cache) {
if (cache.containsKey(str)) {
return cache.get(str);
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch != '+' && ch != '-' && ch != '*') {
continue;
}
String left = str.substring(0, i);
String right = str.substring(i + 1);
List<Integer> leftList = handle(left, cache);
List<Integer> rightList = handle(right, cache);
for (Integer l : leftList) {
for (Integer r : rightList) {
result.add(calculate(ch, l, r));
}
}
}
if (result.size() == 0) {
result.add(Integer.parseInt(str));
}
cache.put(str, result);
return result;
}
private Integer calculate(char ch, Integer left, Integer right) {
if (ch == '+') {
return left + right;
}
if (ch == '-') {
return left - right;
}
if (ch == '*') {
return left * right;
}
throw new IllegalArgumentException("incorrect char");
}
|
