Article / 文章
LeetCode第241题：为运算表达式设计优先级
LeetCode第241题：为运算表达式设计优先级
问题描述
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4 。
难度：中等
示例
示例 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]内
解题思路
本题可以使用分治法（Divide and Conquer）来解决。分治法的思想是把一个复杂的问题分解成若干个相似的子问题，递归解决这些子问题，然后将子问题的解组合起来得到原问题的解。
对于本题，我们可以按照以下步骤解决：
- 遍历表达式，寻找运算符（+、-、*）
- 对于每个运算符，将表达式分成左右两部分
- 递归计算左右两部分所有可能的结果
- 根据当前运算符，对左右两部分的结果进行组合计算
- 如果表达式中没有运算符，说明表达式只包含数字，直接转换为整数返回
方法：分治算法
分治算法的关键在于找到合适的“分”点，这里我们以运算符为分点，将表达式划分为左右两部分，分别递归求解。
代码实现
C#实现
public class Solution {
public IList<int> DiffWaysToCompute(string expression) {
List<int> result = new List<int>();
// 遍历表达式中的每个字符
for (int i = 0; i < expression.Length; i++) {
char c = expression[i];
// 找到运算符
if (c == '+' || c == '-' || c == '*') {
// 分成左右两部分，递归计算所有可能的结果
var leftResults = DiffWaysToCompute(expression.Substring(0, i));
var rightResults = DiffWaysToCompute(expression.Substring(i + 1));
// 组合左右两部分的结果
foreach (var left in leftResults) {
foreach (var right in rightResults) {
if (c == '+') {
result.Add(left + right);
} else if (c == '-') {
result.Add(left - right);
} else if (c == '*') {
result.Add(left * right);
}
}
}
}
}
// 如果没有找到运算符，说明表达式只包含数字
if (result.Count == 0) {
result.Add(int.Parse(expression));
}
return result;
}
}Python实现
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
# 使用备忘录优化递归
memo = {}
def compute(exp):
if exp in memo:
return memo[exp]
result = []
for i in range(len(exp)):
if exp[i] in ['+', '-', '*']:
# 分割表达式
left_results = compute(exp[:i])
right_results = compute(exp[i+1:])
# 根据运算符组合结果
for left in left_results:
for right in right_results:
if exp[i] == '+':
result.append(left + right)
elif exp[i] == '-':
result.append(left - right)
elif exp[i] == '*':
result.append(left * right)
# 如果表达式中没有运算符，则它是一个数字
if not result:
result.append(int(exp))
memo[exp] = result
return result
return compute(expression)C++实现
class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
unordered_map<string, vector<int>> memo;
return compute(expression, memo);
}
private:
vector<int> compute(string expression, unordered_map<string, vector<int>>& memo) {
// 如果已经计算过，直接返回结果
if (memo.count(expression)) {
return memo[expression];
}
vector<int> result;
for (int i = 0; i < expression.length(); i++) {
char c = expression[i];
// 找到运算符
if (c == '+' || c == '-' || c == '*') {
string leftExp = expression.substr(0, i);
string rightExp = expression.substr(i + 1);
// 递归计算左右两部分的结果
vector<int> leftResults = compute(leftExp, memo);
vector<int> rightResults = compute(rightExp, memo);
// 组合左右两部分的结果
for (int left : leftResults) {
for (int right : rightResults) {
if (c == '+') {
result.push_back(left + right);
} else if (c == '-') {
result.push_back(left - right);
} else if (c == '*') {
result.push_back(left * right);
}
}
}
}
}
// 如果没有找到运算符，说明表达式只包含数字
if (result.empty()) {
result.push_back(stoi(expression));
}
// 存储结果以备后用
memo[expression] = result;
return result;
}
};性能分析
时间复杂度
时间复杂度较难精确计算，因为它取决于表达式中运算符的数量和分布。在最坏情况下，如果运算符均匀分布，复杂度可以近似为 O(2^n)，其中n是表达式的长度。这是因为每个运算符都会导致问题分解为两个子问题。
然而，通过使用备忘录（记忆化）优化，我们可以避免重复计算相同的子表达式，从而显著提高效率。优化后的时间复杂度是O(n^3)，其中n是表达式的长度。
空间复杂度
空间复杂度主要由递归调用栈和备忘录占用的空间决定：
- 递归调用栈的深度是O(n)，其中n是表达式的长度
- 备忘录的大小也是O(n^2)，因为最多有n^2个不同的子表达式
因此，总的空间复杂度是O(n^2)。
优化方向
- 记忆化搜索：使用哈希表存储已经计算过的子表达式的结果，避免重复计算
- 预处理数字：可以提前将表达式中的数字和运算符分离出来，避免在递归过程中重复解析
- 动态规划：可以将递归转换为自底向上的动态规划方法
方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 优势 | 劣势 |
|---|---|---|---|---|
| 分治（无缓存） | O(2^n) | O(n) | 实现简单 | 存在大量重复计算 |
| 分治（有缓存） | O(n^3) | O(n^2) | 避免重复计算 | 需要额外空间 |
| 动态规划 | O(n^3) | O(n^2) | 自底向上，无递归栈开销 | 实现较复杂 |