1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/different-ways-to-add-parentheses/description/

2.解题方法

2.1.解题思路

记忆化搜索

2.2.解题步骤

第一步，将所有数和操作符转化为一个数组的形式，记为expArr

第二步，构建记忆化搜索函数。递归自顶向下任务：返回expArr[l:r+1]表达式数组所有可能计算结果数组

第三步，dfs(0,len(expArr)-1)即为题解，调用返回即可

3.解题代码

python代码

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # 思路：记忆化搜索
        map1 = {"+": -1, "-": -2, "*": -3}
        # 第一步，将所有数和操作符转化为一个数组的形式，记为expArr
        expArr = []
        n = len(expression)
        i = 0
        while i < n:
            c = expression[i]
            if c.isdigit():
                num = 0
                while i < n and expression[i].isdigit():
                    num = num * 10 + int(expression[i])
                    i += 1
                expArr.append(num)
            else:
                expArr.append(map1[c])
                i += 1
        # print(expArr)
        # 第二步，构建记忆化搜索函数。递归自顶向下任务：返回expArr[l:r+1]表达式数组所有可能计算结果数组
        @lru_cache
        def dfs(l:int, r:int) -> List[int]:
            if l == r:
                return [expArr[l]]
            ans = []
            for i in range(l, r, 2):
                lans = dfs(l, i)
                rans = dfs(i + 2, r)
                for lval in lans:
                    for rval in rans:
                        if expArr[i + 1] == -1:
                            ans.append(lval + rval)
                        elif expArr[i + 1] == -2:
                            ans.append(lval - rval)
                        elif expArr[i + 1] == -3:
                            ans.append(lval * rval)
            return ans
        # 第三步，dfs(0,len(expArr)-1)即为题解，调用返回即可
        return dfs(0, len(expArr) - 1)

4.执行结果