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

Categories:

题目描述
思路分析
1. 解法一：分治 + 记忆化（推荐）
相似题目

题目描述

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

思路分析

解法一：分治 + 记忆化（推荐）

核心思路：

遍历表达式中的运算符，将表达式拆成左右两部分递归求值。

左右结果两两组合得到当前表达式所有结果。

使用哈希表记忆化避免重复计算。

复杂度分析：

时间复杂度：O(C_n)，其中 C_n 为卡特兰数数量级。

空间复杂度：O(C_n)，存储所有子问题结果。

class Solution {
    private final 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> res = new ArrayList<>();
        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 == '+') {
                            res.add(a + b);
                        } else if (c == '-') {
                            res.add(a - b);
                        } else {
                            res.add(a * b);
                        }
                    }
                }
            }
        }

        if (res.isEmpty()) {
            res.add(Integer.parseInt(exp));
        }

        memo.put(exp, res);
        return res;
    }
}

func diffWaysToCompute(expression string) []int {
	memo := make(map[string][]int)

	var dfs func(string) []int
	dfs = func(exp string) []int {
		if v, ok := memo[exp]; ok {
			return v
		}

		res := make([]int, 0)
		for i := 0; i < len(exp); i++ {
			c := exp[i]
			if c == '+' || c == '-' || c == '*' {
				left := dfs(exp[:i])
				right := dfs(exp[i+1:])

				// 左右结果组合
				for _, a := range left {
					for _, b := range right {
						switch c {
						case '+':
							res = append(res, a+b)
						case '-':
							res = append(res, a-b)
						case '*':
							res = append(res, a*b)
						}
					}
				}
			}
		}

		if len(res) == 0 {
			val, _ := strconv.Atoi(exp)
			res = append(res, val)
		}

		memo[exp] = res
		return res
	}

	return dfs(expression)
}

相似题目

题目	难度	考察点
95. 不同的二叉搜索树 II	中等	分治
241. 为运算表达式设计优先级	中等	分治
282. 给表达式添加运算符	困难	回溯
312. 戳气球	困难	区间 DP
87. 扰乱字符串	困难	递归 + 记忆化

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/98576916