241. different ways to add parentheses

class Solution:
    def diffWaysToCompute(self, input):
        if input.isdigit():
            return [int(input)]
        res = []
        for i in range(len(input)):
            if input[i] in '+-*':
                res1 = self.diffWaysToCompute(input[:i])
                res2 = self.diffWaysToCompute(input[i+1:])
                res.extend(self.calc(j, k, input[i]) for j in res1 for k in res2)
        return res

    def calc(self, x, y, op):
        if op == '+':
            return x + y
        elif op == '-':
            return x - y
        else:
            return x * y

def diffWaysToCompute(self, input):
    return [a+b if c == '+' else a-b if c == '-' else a*b
            for i, c in enumerate(input) if c in '+-*'
            for a in self.diffWaysToCompute(input[:i])
            for b in self.diffWaysToCompute(input[i+1:])] or [int(input)]

class Solution:
    def diffWaysToCompute(self, input):
        memo = {}
        def dfs(input):
            if input.isdigit():
                return [int(input)]
            if input in memo:
                return memo[input]
            res = []
            for i in range(len(input)):
                if input[i] == '+':
                    for left in dfs(input[:i]):
                        for right in dfs(input[i+1:]):
                            res.append(left+right)    
                elif input[i] == '-':
                    for left in dfs(input[:i]):
                        for right in dfs(input[i+1:]):
                            res.append(left-right)
                elif input[i] == '*':
                    for left in dfs(input[:i]):
                        for right in dfs(input[i+1:]):
                            res.append(left*right)
            memo[input] = res
            return memo[input]
        return dfs(input)