241. Different Ways to Add Paren
2016-12-18 本文已影响0人
阿团相信梦想都能实现
class Solution(object):
def __init__(self):
self.res_hash=dict()
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
if input.isdigit():return [int(input)]
if input in self.res_hash:
print 'reused result for',input
return self.res_hash[input]
res=[]
for i in range(len(input)):
if input[i] in '+-*':
res1=self.diffWaysToCompute(input[:i])
res2=self.diffWaysToCompute(input[i+1:])
for a in res1:
for b in res2:
res.append(self.helper(a,b,input[i]))
self.res_hash[input]=res
return res
def helper(self,num1,num2,operator):
if operator=='+':
return num1+num2
elif operator=='-':
return num1-num2
else:
return num1*num2