leetcode 241Different Ways to Add Parentheses 为运算表达式设计优先级 解题记录

241 Different Ways to Add Parentheses
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 104.

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

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

经典分治题，核心就是一句话， 任何计算都是 a+b, a-b, a*b, a/b, 所以，分治就是左边一坨，右边一坨，然后左右的就丢给recursion来解决。

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        if expression.isdigit():
            return [int(expression)]
        res = []
        for i in range(len(expression)):
            if expression[i] in "+-*/":
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i+1:])
                for j in left:
                    for k in right:
                        if expression[i] == "+":
                            res.append(j + k)
                        elif expression[i] == "-":
                            res.append(j - k)
                            
                        elif expression[i] == "*":
                            res.append(j * k)
        return res  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19