LeetCode 241. 为运算表达式设计优先级

2025-10-23 HGNULB 约 6 分钟

文章信息 8 个分类 6 个标签

分类

题目描述

✅ 241. 为运算表达式设计优先级

题意分析

给出一个只含非负整数和 +、-、* 三种运算符的表达式字符串，要求把所有可能的加括号方式对应的计算结果全部列出来。返回顺序任意。

要点在于「所有可能的加括号方式」等价于「所有可能的运算次序」。加括号不会改变数字和运算符的排列，只改变谁先算谁后算，因此答案的数量就是把这串运算符排成一棵二叉运算树的方案数。

约束信号：表达式长度不超过 20，其中的整数取值在 $[0, 99]$，所以运算符最多只有 9 个左右，方案数是可以承受的指数级；同时题目保证结果和所有中间值都在 32 位整数范围内，不必担心溢出。

边界情况：表达式可能完全没有运算符，此时它就是一个数字，答案是只含该数字的列表；数字可能是两位数，扫描时不能按单个字符解析；结果允许重复，两种不同的加括号方式算出同一个值时要各计一次，不能去重。

解法：分治枚举最后运算符 + 记忆化

核心思路

与其枚举括号，不如枚举最后执行的运算符。任意完整加括号方案都对应一棵二叉运算树，最后执行的运算符就是根；固定根以后，左右子表达式可以独立求解，正好形成分治。

定义 $F(s)$ 为子表达式 $s$ 的全部可能结果，结果按列表保存，允许重复。枚举 $s$ 中每个运算符 op：递归得到左右结果列表，再对二者做笛卡尔积，把每个 a op b 加入答案。若没有找到运算符，说明 $s$ 是一个完整数字，直接解析为整数。

完备性来自根运算符的唯一性：任意括号方案都有且只有一个根，必然落入某个分割点；固定根后，递归又枚举了左右两侧的全部方案，因此不漏。不同运算树即使算出相同数值，也代表不同括号方案，所以只拼接列表，不能去重。

同一子表达式会由不同分割路径反复求解，例如 2*3-4*5 中的 3-4。用子串作为键记忆化，每个子问题只展开一次；本题字符串很短，无需额外解析成令牌或设计区间键。

解题步骤

建立 memo，记录每个子表达式对应的结果列表；递归开始时先查缓存。

扫描当前子串，遇到 +、- 或 * 时，把它作为最后执行的运算符。

递归求左右子串，对左右结果做笛卡尔积，并按当前运算符合并。减法不能交换操作数顺序。

若整段没有运算符，将其作为多位整数解析，这是递归基准。

缓存当前列表后返回；列表中的重复值必须保留。

以 2*3-4*5 为例，三个根运算符依次贡献 [-34, -10]、[-14]、[-10, 10]，合并得到 5 个结果。两个 -10 来自不同运算树，正是题目要求的两个答案。

代码实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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$ 个结果；记忆化后，各区间结果的组合总量与 $C_n$ 同阶，因此时间为 $O(C_n)$，另有扫描和截取子串的多项式开销。

空间复杂度：$O(C_n)$。缓存保存各子表达式的结果列表，递归深度为 $O(n)$；卡特兰规模是主导项。

关键点总结

把括号方案看成二叉运算树，枚举最后运算符就是枚举根节点。

子问题返回结果列表，合并方式是左右列表的笛卡尔积。

根节点唯一保证枚举不漏；数值相同不代表方案相同，因此不能去重。

记忆化消除重复子表达式，复杂度下界仍由卡特兰数量级的输出决定。

面试时重点讲清“为什么枚举最后运算符完备”，而不只是写出递归代码。

易错点总结

右子串必须从运算符后一位开始；写成 substring(i) 会让递归无法缩小。

基准条件是“没有运算符”，不是“长度为 1”，否则 11 这样的多位数会返回空列表。

结果不能放入集合去重；2*3-4*5 中两个 -10 对应两种合法括号方案。

左右操作数不能调换，2-3 与 3-2 的结果不同。

缓存必须在递归入口读取、返回前写入，否则重复区间仍会被指数级展开。

相似题目

题目	难度	考察点
95. 不同的二叉搜索树 II	中等	同样枚举根节点，但要构造出全部树而非求值
22. 括号生成	中等	回溯生成合法括号串，靠左右计数剪枝
227. 基本计算器 II	中等	固定优先级下用栈求值，只需一个确定答案
1106. 解析布尔表达式	困难	括号已给定，重点是嵌套结构的递归下降解析