241. 为运算表达式设计优先级(分治 +记忆化)

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

给你一个由数字和运算符组成的字符串 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-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

思路

采用分治法将表达式进行递归分解。每次遇到一个运算符，就把表达式分成左右两部分。左部分和右部分分别递归计算，然后根据当前的运算符组合它们的结果。同时使用记忆化来记录每次计算的结果，避免重复计算。

Code

class Solution {
public:
    unordered_map<string,vector<int>> memo ; 
    vector<int> diffWaysToCompute(string expression) {
                int n = expression.size() ; 
        if(memo.count(expression) ) {
            return memo[expression] ; 
        }
        vector<int> res ; // 记录
        for(int i = 0 ; i<n ; i ++){
            char ch = expression[i] ; 
            if( !isdigit(ch)) {
                vector<int> left = diffWaysToCompute(expression.substr(0,i)) ; 
                vector<int> right = diffWaysToCompute(expression.substr(i+1) ) ; 

                for(int a : left ) {
                    for(int b : right) {
                        if(ch =='+') {
                            res.push_back(a+b) ; 
                        }else if(ch == '-') {
                            res.push_back(a-b) ; 
                        }else if(ch == '*') {
                            res.push_back(a*b) ; 
                        }
                    }
                }

            }
        }
        if(res.empty()) {
            res.push_back(stoi(expression) ); 
        }
        memo[expression] = res ; 
        return res ; 

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38