Bottom-up DP solution in Python, beats 98%


  • 5
    import operator, re
    ops = {'+': operator.add, '-': operator.sub, '*': operator.mul}
    
    class Solution(object):
        def diffWaysToCompute(self, s):
            nums = [int(x) for x in re.findall(r'[0-9]+', s)]
            opers = re.findall(r'\+|\-|\*', s)
            n, DP = len(nums), {}
            for i in range(n):
                DP[i, i] = [nums[i]]
            for i in range(n - 1):
                DP[i, i+1] = [ops[opers[i]](nums[i], nums[i + 1])]
            for k in range(3, n + 1):
                for i in range(n - k + 1):
                    j = i + k - 1
                    DP[i, j] = []
                    for v in range(i, j):
                        left = DP[i, v]
                        right = DP[v + 1, j]
                        for e1 in left:
                            for e2 in right:
                                DP[i, j].append(ops[opers[v]](e1, e2))
            return DP[0, n - 1]
    

    We can't do better than exponential time because the size of the result is the Catalan number. But we can solve recursively and store partial results in order to not recompute results that we already know.

    This problem is very similar to Different Number of BSTs that you can build from 1 to n (same thing, it's the Catalan number)


  • 0
    W
    DP = [[] for j in range(len(nums))] for i in range(len(nums))]#maybe more good.

Log in to reply
 

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