241. 为运算表达式设计优先级
https://leetcode.cn/problems/different-ways-to-add-parentheses/
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
输入：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) = 1
结题思路:递归法求解,当然官解上也有好多dp的解法,但是感觉相对繁琐.回溯法忘得差不多了,这次还是参考了别人的思路才做出来的…….
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
res = []
ops = {'+':lambda x,y : x+y,'-':lambda x,y : x-y, '*':lambda x,y : x*y}
for index in range(1, len(expression) - 1):
if expression[index] in ops:
for left in self.diffWaysToCompute(expression[:index]):
for right in self.diffWaysToCompute(expression[index+1:]):
res.append(ops[expression[index]](left,right))
if not res:
res.append(int(expression))
return res举例图如下:
从图中可以看到,每次都是递归到最下层,然后将最下层的值,返回到上一层,
-
举例：
a + (b - (c * d))会不断的变成a + (b - (res1 * res2))->a + (res1 - res2)->res1 + res2
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/88900.html
