Leetcode 241. Different Ways to Add Parentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/

The main thought is to divide two parts when encountering a operator. And to avoid repeated calculation, we establish a lookup table to store calculated result.

Solution:

# T:O(n * Catalan numbers) S:O(n * Catalan numbers)
class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        lookup = [[None for _ in xrange(len(input) + 1)] for _ in xrange(len(input) + 1)]
        ops = {'+': operator.add, '-': operator.sub, '*': operator.mul}

        def diffWaysToComputeRecu(left, right):
            if lookup[left][right]:
                return lookup[left][right]
            result = []
            for i in xrange(left, right):
                if input[i] in ops:
                    for x in diffWaysToComputeRecu(left, i):
                        for y in diffWaysToComputeRecu(i + 1, right):
                            result.append(ops[input[i]](x, y))
            
            if not result:
                result = [int(input[left:right])]
            lookup[left][right] = result     
            return lookup[left][right]
            
        return diffWaysToComputeRecu(0, len(input))

Run Time: 60 ms