class Solution:
def diffWaysToCompute(self, input: str) -> List[int]:
string_len = len(input)
n, a, b = 0, 0, 0
nums, symbols = [], []
while b < string_len:
if input[b] in ('+', '-', '*'):
if b > a:
nums.append(int(input[a: b]))
symbols.append(input[b])
a = b = b + 1
else:
b += 1
if b > a:
nums.append(int(input[a: b]))
n, m = len(symbols), len(nums)
if n == 0:
return nums
if n != m - 1:
return [0]
@functools.lru_cache() # 缓存加速
def get_res(start, end):
if start == end:
return [eval('{}{}{}'.format(nums[start - 1], symbols[start - 1], nums[start]))]
res = []
for i in range(start, end + 1):
left_res = get_res(start, i - 1) if i > start else [nums[start - 1]]
right_res = get_res(i + 1, end) if i < end else [nums[end]]
for l in left_res:
for r in right_res:
res.append(eval('{}{}{}'.format(l, symbols[i - 1], r)))
return res
return get_res(1, n) if n else [0]