Python DP(Memoization) beats 99%


  • 0
    E

    Think from the end. What is the last operation and recurse left and right. Than merge the results. Since there are overlapping subproblems memoizaiton helps.

    import operator as op
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        self.mem={}
        return self.helper(input)
        
    def helper(self,s):
        if s in self.mem:
            return self.mem[s]
        elif s.isdigit():
            return [int(s)]
        else:
            res = [ ]
            for i in xrange(1,len(s)):
                if s[i].isdigit():
                    continue        
                a1 = self.helper(s[0:i])
                a2 = self.helper(s[(i+1):])
                if s[i] == '+':
                    my_op = op.add
                elif s[i] == '-':
                    my_op = op.sub
                elif s[i] == '*':
                    my_op = op.mul
                for e1 in a1:
                    for e2 in a2:
                        res.append(my_op(e1,e2))
            self.mem[s] = res
            return res

Log in to reply
 

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