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

🟠   🔖  递归 记忆化搜索 数学 字符串 动态规划  🔗 力扣 LeetCode

题目

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10^4.

Example 1:

Input: expression = "2-1-1"

Output: [0,2]

Explanation:

((2-1)-1) = 0

(2-(1-1)) = 2

Example 2:

Input: expression = "23-45"

Output: [-34,-14,-10,-10,10]

Explanation:

(2*(3-(4*5))) = -34

((23)-(45)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

Constraints:

• 1 <= expression.length <= 20
• expression consists of digits and the operator '+', '-', and '*'.
• All the integer values in the input expression are in the range [0, 99].
• The integer values in the input expression do not have a leading '-' or '+' denoting the sign.

题目大意

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4 。

示例 1：

输入： expression = "2-1-1"

输出：[0,2]

解释：

((2-1)-1) = 0

(2-(1-1)) = 2

示例 2：

输入： expression = "23-45"

输出：[-34,-14,-10,-10,10]

解释：

(2*(3-(4*5))) = -34

((23)-(45)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

提示：

• 1 <= expression.length <= 20
• expression 由数字和算符 '+'、'-' 和 '*' 组成。
• 输入表达式中的所有整数值在范围 [0, 99]
• 输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。

解题思路

1. 分治法

• 分而治之的思想：将问题划分为更小的子问题，分别计算子表达式的结果，再组合成最终结果。
• 对每个操作符，将表达式分为两部分：
  • 左侧子表达式
  • 右侧子表达式
• 分别递归计算两部分的结果，然后通过操作符组合所有可能的结果。

2. 递归过程

• 遍历字符串，遇到操作符时，将表达式划分为两部分。
• 对每部分递归调用 diffWaysToCompute。
• 对返回的子结果集合，按照当前操作符进行组合运算。
• 如果字符串中没有操作符，直接将字符串转为数字并返回。

3. 递归终止条件

• 如果表达式中没有操作符，说明已经是最小子问题，直接返回该数字。

复杂度分析

• 时间复杂度：O(2^n)，每次递归会将表达式拆分成左右两部分，递归深度为 O(n)，且每层递归会对所有操作符进行分治，导致总复杂度为指数级增长。
• 空间复杂度：O(n)，递归调用栈所占用的空间。

代码

/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function (expression) {
	let res = []; // 存储所有可能的结果

	// 遍历表达式字符串
	for (let i = 0; i < expression.length; i++) {
		const char = expression[i];

		// 如果当前字符是操作符
		if (char === '+' || char === '-' || char === '*') {
			// 分别计算左右两部分的结果
			const res1 = diffWaysToCompute(expression.slice(0, i));
			const res2 = diffWaysToCompute(expression.slice(i + 1));

			// 组合左右两部分的结果
			for (let i of res1) {
				for (let j of res2) {
					if (char === '+') res.push(i + j);
					else if (char === '-') res.push(i - j);
					else if (char === '*') res.push(i * j);
				}
			}
		}
	}

	// 如果结果集为空，说明当前表达式是一个数字
	if (res.length === 0) res.push(Number(expression));

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
95	不同的二叉搜索树 II	[✓]	树 二叉搜索树 动态规划 2+	🟠	🀄️ 🔗
224	基本计算器	[✓]	栈 递归 数学 1+	🔴	🀄️ 🔗
282	给表达式添加运算符		数学 字符串 回溯	🔴	🀄️ 🔗
2019	解出数学表达式的学生分数		栈 记忆化搜索 数组 3+	🔴	🀄️ 🔗
2232	向表达式添加括号后的最小结果		字符串 枚举	🟠	🀄️ 🔗