LeetCode 241. 为运算表达式设计优先级
题目描述
题意分析
保持数字和运算符的原有顺序，通过改变括号位置决定运算次序，返回所有括号方案的计算结果。题目不是求一个最大值或最小值，也不是按通常的乘法优先规则计算一次。
不同方案可能得到相同数值，这些结果仍要分别保留。输入中的整数不带正负号，所以每个
+、-、*都是连接左右两个子表达式的运算符，多位数字则必须作为一个整体。
解法：分治枚举最后运算符 + 记忆化
核心思路
[!blue]
直接枚举括号放在哪些字符间很难避免遗漏。换一个角度：无论括号怎样安排，整个表达式总有一次最后执行的运算。设它位于下标
i，那么它左边和右边的子表达式都必须先算完，再用这个运算符合并。定义
dfs(expr)返回子表达式expr的全部计算结果。扫描expr中的每个运算符，把它依次视为最后一次运算，递归求出左右结果列表left和right。左侧的任意一种括号方案都能与右侧的任意一种方案搭配，因此需要两层循环，枚举每个a与每个b，追加a op b。这种拆法既完整又不会重复枚举同一方案：每个完整括号方案都有唯一的最后运算符，它对应一次确定的切分；该切分下的左右括号方案再由递归分别枚举。反过来，每一对左右方案也都能由当前运算符合法连接。相同数值可能来自不同方案，因此列表不能去重。
如果整段没有运算符，它就是一个完整整数，直接解析并返回只含这个数的列表，这是递归终点。不能以字符串长度是否为 $1$ 判断终点，因为输入也可能包含多位数。代码中，有运算符的合法子表达式至少能组合出一个结果，所以
res为空恰好表示没有遇到运算符。不同切分会反复求解相同的子表达式，用
memo按字符串内容缓存整个结果列表。缓存命中时直接读取；父问题仍照常枚举列表中的每一项，所以复用计算不会丢失括号方案的数量。左右子串都比原串短，递归最终一定到达整数。
解题步骤
- 建立
memo，记录每个子表达式对应的结果列表；递归开始时先查缓存。- 扫描当前子串，遇到
+、-或*时，把它作为最后执行的运算符。- 递归求左右子串，对左右结果做笛卡尔积，并按当前运算符合并。减法不能交换操作数顺序。
- 若整段没有运算符，将其作为多位整数解析，这是递归基准。
- 缓存当前列表后返回；列表中的重复值必须保留。
代码实现
class Solution {
public List<Integer> diffWaysToCompute(String expression) {
return dfs(expression, new HashMap<>());
}
private List<Integer> dfs(String expression, Map<String, List<Integer>> memo) {
if (memo.containsKey(expression)) {
return memo.get(expression);
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
char op = expression.charAt(i);
if (op != '+' && op != '-' && op != '*') {
continue;
}
// 枚举最后一次执行的运算符，左右两侧结果再两两组合。
List<Integer> left = dfs(expression.substring(0, i), memo);
List<Integer> right = dfs(expression.substring(i + 1), memo);
// 不同括号方案即使数值相同也分别保留，不能对组合结果去重。
for (int a : left) {
for (int b : right) {
res.add(calculate(a, b, op));
}
}
}
// 没有运算符时把整段作为一个数解析，也包含多位数。
if (res.isEmpty()) {
res.add(Integer.parseInt(expression));
}
memo.put(expression, res);
return res;
}
private int calculate(int a, int b, char op) {
if (op == '+') {
return a + b;
}
if (op == '-') {
return a - b;
}
return a * b;
}
}
import "strconv"
func diffWaysToCompute(expression string) []int {
memo := make(map[string][]int)
var dfs func(expr string) []int
dfs = func(expr string) []int {
if res, ok := memo[expr]; ok {
return res
}
res := make([]int, 0)
for i := 0; i < len(expr); i++ {
op := expr[i]
if op != '+' && op != '-' && op != '*' {
continue
}
// 枚举最后一次执行的运算符，左右两侧结果再两两组合。
left := dfs(expr[:i])
right := dfs(expr[i+1:])
// 不同括号方案即使数值相同也分别保留，不能对组合结果去重。
for _, a := range left {
for _, b := range right {
res = append(res, calcExpr(a, b, op))
}
}
}
// 没有运算符时把整段作为一个数解析，也包含多位数。
if len(res) == 0 {
value, _ := strconv.Atoi(expr)
res = append(res, value)
}
memo[expr] = res
return res
}
return dfs(expression)
}
func calcExpr(a int, b int, op byte) int {
if op == '+' {
return a + b
}
if op == '-' {
return a - b
}
return a * b
}
复杂度分析
- 时间复杂度：设运算符数为 $n$，完整括号方案数为卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$，即使数值相同，也要输出这 $C_n$ 项。含 $k$ 个运算符的区间至多有 $n-k+1$ 个，每个区间生成 $C_k$ 个结果；缓存后所有区间的组合总量至多为 $\sum_{k=0}^{n}(n-k+1)C_k = O(C_n)$。扫描、字符串截取及哈希还有多项式开销，整体由指数增长的 $C_n$ 主导。
- 空间复杂度：$O(C_n)$。各区间缓存的结果总数同样是 $O(C_n)$，递归深度为 $O(n)$；记忆化减少重复计算，但不能减少题目要求返回的方案数。
关键点总结
[!green]
- 把括号方案看成二叉运算树，枚举最后运算符就是枚举根节点。
- 子问题返回结果列表，合并方式是左右列表的笛卡尔积。
- 根节点唯一保证枚举不漏；数值相同不代表方案相同，因此不能去重。
- 记忆化消除重复子表达式，复杂度下界仍由卡特兰数量级的输出决定。
易错点总结
[!yellow]
- 右子串必须从运算符后一位开始；写成
substring(i)会让递归无法缩小。- 基准条件是“没有运算符”，不是“长度为 1”，否则
11这样的多位数会返回空列表。- 结果不能放入集合去重；相同数值仍可能对应不同括号方案。
- 左右操作数不能调换，减法的方向必须与原表达式一致。
- 缓存必须在递归入口读取、返回前写入，否则重复区间仍会被指数级展开。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 08.14. 布尔运算 | 中等 | 同样枚举最后运算符并组合两侧结果，布尔题可把结果压缩为0和1的计数。 |