# recursive python using indices and memorization, beating 94%

• The naive one is similar to other people's posts, but it uses indices instead of many substrings for the sake of reducing O(n) in substring. The following beats 45%.

``````class Solution(object):
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
return self.divideAndConquer(input, 0, len(input))

def divideAndConquer(self, input, start, end):
if start >= end:
return []
res = []
for i in range(start, end):
if input[i] in ('+', '-', '*'):
left = self.divideAndConquer(input, start, i)
right = self.divideAndConquer(input, i + 1, end)
for a in left:
for b in right:
n = a + b if input[i] == '+' else (a - b if input[i] == '-' else a * b)
res.append(n)
return res if res else [int(input[start:end])]
``````

Then the further improved one is using memorization, and it speeds up much more, beating 94%:

``````class Solution(object):
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
return self.divideAndConquer(input, 0, len(input), {})

def divideAndConquer(self, input, start, end, memo):
if start >= end:
return []
if (start, end) in memo:
return memo[(start, end)]
res = []
for i in range(start, end):
if input[i] in ('+', '-', '*'):
left = self.divideAndConquer(input, start, i, memo)
right = self.divideAndConquer(input, i + 1, end, memo)
for a in left:
for b in right:
n = a + b if input[i] == '+' else (a - b if input[i] == '-' else a * b)
res.append(n)
memo[(start, end)] = res if res else [int(input[start:end])]
return memo[(start, end)]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.