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

题目描述

本题目来自LeetCode上的『241. 为运算表达式设计优先级』

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

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

示例1：

输入：expression = “23-45”
输出：[-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]

题解

不失一般性，以加法为例，对于表达式 $A + B$，将其以加号为分界，分成 $A$ 和 $B$ 两部分表达式，对于每一个表达式，再进行上述分治方法。
设递归函数 dfs(string str)，如果 str 是一个数字，那么直接返回这个数字，否则将其根据运算符分成两部分进行递归。
数据量不大，可以爆搜，也可以使用记忆化递归。

代码

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:

        @cache
        def dfs(expression: str) -> List[int]:
            if expression.isdigit():
                return [int(expression)]
            ans = []
            for i, op in enumerate(expression):
                if op == '+' or op == '-' or op == '*':
                    l = dfs(expression[:i])
                    r = dfs(expression[i + 1:])
                    for item in itertools.product(l, r):
                        if op == '+':
                            ans.append(item[0] + item[1])
                        elif op == '-':
                            ans.append(item[0] - item[1])
                        elif op == '*':
                            ans.append(item[0] * item[1])
            return ans
        
        return dfs(expression)