Medium

题目描述

给你一个由数字和运算符组成的字符串 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 <= 20
  • expression 由数字和运算符 '+'、'-'、'*' 组成
  • 输入表达式中的所有整数值在范围 [0, 99] 内
  • 输入表达式中的整数值都不含前导 '-' 或 '+'

解题思路

这是一个典型的分治问题，核心思想是通过递归分解来解决。

解题思路：

  1. 分治策略：对于表达式中的每一个运算符，我们可以将表达式分为左右两部分，分别计算左右部分的所有可能结果，然后将它们组合。

  2. 递归过程：

    • 遍历表达式中的每个运算符
    • 以该运算符为分界点，将表达式分成左右两个子表达式
    • 递归计算左右子表达式的所有可能结果
    • 根据运算符将左右结果组合得到当前表达式的所有可能结果

  3. 边界条件：当表达式中没有运算符时，说明是一个纯数字，直接返回该数字。

  4. 优化策略：可以使用记忆化搜索来避免重复计算相同的子表达式。

算法流程：

  • 如果表达式只包含数字，直接返回
  • 否则遍历每个运算符位置，递归计算左右子表达式
  • 将左右结果通过当前运算符组合，得到所有可能的结果

这种方法时间复杂度较高，但对于题目给定的约束条件（表达式长度不超过20）是可以接受的。

代码实现

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> result;
        
        for (int i = 0; i < expression.length(); i++) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            result.push_back(l + r);
                        } else if (c == '-') {
                            result.push_back(l - r);
                        } else if (c == '*') {
                            result.push_back(l * r);
                        }
                    }
                }
            }
        }
        
        if (result.empty()) {
            result.push_back(stoi(expression));
        }
        
        return result;
    }
};

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        result = []
        
        for i in range(len(expression)):
            c = expression[i]
            if c in '+-*':
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i+1:])
                
                for l in left:
                    for r in right:
                        if c == '+':
                            result.append(l + r)
                        elif c == '-':
                            result.append(l - r)
                        elif c == '*':
                            result.append(l * r)
        
        if not result:
            result.append(int(expression))
        
        return result

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 left = DiffWaysToCompute(expression.Substring(0, i));
                var right = DiffWaysToCompute(expression.Substring(i + 1));
                
                foreach (int l in left) {
                    foreach (int r in right) {
                        if (c == '+') {
                            result.Add(l + r);
                        } else if (c == '-') {
                            result.Add(l - r);
                        } else if (c == '*') {
                            result.Add(l * r);
                        }
                    }
                }
            }
        }
        
        if (result.Count == 0) {
            result.Add(int.Parse(expression));
        }
        
        return result;
    }
}

var diffWaysToCompute = function(expression) {
    const memo = new Map();
    
    function compute(expr) {
        if (memo.has(expr)) {
            return memo.get(expr);
        }
        
        const result = [];
        
        for (let i = 0; i < expr.length; i++) {
            const char = expr[i];
            if (char === '+' || char === '-' || char === '*') {
                const left = compute(expr.substring(0, i));
                const right = compute(expr.substring(i + 1));
                
                for (const l of left) {
                    for (const r of right) {
                        if (char === '+') {
                            result.push(l + r);
                        } else if (char === '-') {
                            result.push(l - r);
                        } else {
                            result.push(l * r);
                        }
                    }
                }
            }
        }
        
        if (result.length === 0) {
            result.push(parseInt(expr));
        }
        
        memo.set(expr, result);
        return result;
    }
    
    return compute(expression);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(4^n)，其中 n 是运算符的数量。在最坏情况下，每个运算符都可能产生指数级的分支
空间复杂度O(4^n)，递归调用栈的深度和存储结果所需的空间

相关题目