题目描述
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
示例 1：
输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2：
输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(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
提示：
1 <= expression.length <= 20expression 由数字和算符 '+'、'-' 和 '*' 组成。- 输入表达式中的所有整数值在范围
[0, 99]
- 输入表达式中的所有整数都没有前导
'-' 或 '+' 表示符号。
解法
方法一：记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
@cache
def dfs(exp):
if exp.isdigit():
return [int(exp)]
ans = []
for i, c in enumerate(exp):
if c in '-+*':
left, right = dfs(exp[:i]), dfs(exp[i + 1 :])
for a in left:
for b in right:
if c == '-':
ans.append(a - b)
elif c == '+':
ans.append(a + b)
else:
ans.append(a * b)
return ans
return dfs(expression)
|
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 | class Solution {
private static Map<String, List<Integer>> memo = new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
return dfs(expression);
}
private List<Integer> dfs(String exp) {
if (memo.containsKey(exp)) {
return memo.get(exp);
}
List<Integer> ans = new ArrayList<>();
if (exp.length() < 3) {
ans.add(Integer.parseInt(exp));
return ans;
}
for (int i = 0; i < exp.length(); ++i) {
char c = exp.charAt(i);
if (c == '-' || c == '+' || c == '*') {
List<Integer> left = dfs(exp.substring(0, i));
List<Integer> right = dfs(exp.substring(i + 1));
for (int a : left) {
for (int b : right) {
if (c == '-') {
ans.add(a - b);
} else if (c == '+') {
ans.add(a + b);
} else {
ans.add(a * b);
}
}
}
}
}
memo.put(exp, ans);
return ans;
}
}
|
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 | class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
return dfs(expression);
}
vector<int> dfs(string exp) {
if (memo.count(exp)) return memo[exp];
if (exp.size() < 3) return {stoi(exp)};
vector<int> ans;
int n = exp.size();
for (int i = 0; i < n; ++i) {
char c = exp[i];
if (c == '-' || c == '+' || c == '*') {
vector<int> left = dfs(exp.substr(0, i));
vector<int> right = dfs(exp.substr(i + 1, n - i - 1));
for (int& a : left) {
for (int& b : right) {
if (c == '-')
ans.push_back(a - b);
else if (c == '+')
ans.push_back(a + b);
else
ans.push_back(a * b);
}
}
}
}
memo[exp] = ans;
return ans;
}
private:
unordered_map<string, vector<int>> memo;
};
|
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 | var memo = map[string][]int{}
func diffWaysToCompute(expression string) []int {
return dfs(expression)
}
func dfs(exp string) []int {
if v, ok := memo[exp]; ok {
return v
}
if len(exp) < 3 {
v, _ := strconv.Atoi(exp)
return []int{v}
}
ans := []int{}
for i, c := range exp {
if c == '-' || c == '+' || c == '*' {
left, right := dfs(exp[:i]), dfs(exp[i+1:])
for _, a := range left {
for _, b := range right {
if c == '-' {
ans = append(ans, a-b)
} else if c == '+' {
ans = append(ans, a+b)
} else {
ans = append(ans, a*b)
}
}
}
}
}
memo[exp] = ans
return ans
}
|
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | using System.Collections.Generic;
public class Solution {
public IList<int> DiffWaysToCompute(string input) {
var values = new List<int>();
var operators = new List<char>();
var sum = 0;
foreach (var ch in input)
{
if (ch == '+' || ch == '-' || ch == '*')
{
values.Add(sum);
operators.Add(ch);
sum = 0;
}
else
{
sum = sum * 10 + ch - '0';
}
}
values.Add(sum);
var f = new List<int>[values.Count, values.Count];
for (var i = 0; i < values.Count; ++i)
{
f[i, i] = new List<int> { values[i] };
}
for (var diff = 1; diff < values.Count; ++diff)
{
for (var left = 0; left + diff < values.Count; ++left)
{
var right = left + diff;
f[left, right] = new List<int>();
for (var i = left; i < right; ++i)
{
foreach (var leftValue in f[left, i])
{
foreach (var rightValue in f[i + 1, right])
{
switch (operators[i])
{
case '+':
f[left, right].Add(leftValue + rightValue);
break;
case '-':
f[left, right].Add(leftValue - rightValue);
break;
case '*':
f[left, right].Add(leftValue * rightValue);
break;
}
}
}
}
}
}
return f[0, values.Count - 1];
}
}
|