Leetcode-241 —— different ways to add parentheses

题目描述

给定一个有数字和运算符组成的字符串,计算不同优先级的情况下的返回结果。

Example 1:

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation:
(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

分析

对于每个运算表达式,我们可以分解为 A op B 的形式。当 AB 都是数字时,直接返回计算结果,否则拆分表达式。

1
2
2*3-4*5 split to =>
(2) * (B) or (2*3)-(B)

所以如下递归求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def calc(x, op, y):
if op == "+":
return x + y
if op == "-":
return x - y
else:
return x * y

def solve(input):
if input.isdigit():
return [int(input)]
ans = []
for i, c in enumerate(input):
if c in "+-*":
left = solve(input[:i])
right = solve(input[i+1:])

for l in left:
for r in right:
ans.append(calc(l, c, r))
return ans

本文标题:Leetcode-241 —— different ways to add parentheses

文章作者:Pylon, Syncher

发布时间:2019年12月15日 - 10:12

最后更新:2020年05月19日 - 22:05

原始链接:https://0x400.com/2019-12-15-lc-241-different-ways-to-add-parentheses.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。