python dp solution with divide and conquer method


  • 0
    V
    class Solution(object):
        
        def dpHelper(self, input, dp):
            length = len(input)
            if dp.has_key(input):
                return dp[input]
            
            # check for numbers
            if "+" not in input and "-" not in input and "*" not in input:
                return [int(input)]
            
            res = []
            for i in xrange(0, length):
                c = input[i]
                if c in "+-*":
                    # divide the string from the operator,
                    # calculate all possible results from left part and right part
                    # for all results of left, do +, - or * with all results of right part
                    # nested loop
                    temp = [ a+b if c == '+' else a-b if c == '-' else a*b
                            for a in self.dpHelper(input[:i], dp)
                            for b in self.dpHelper(input[i+1:], dp) ]
                    res += temp
            dp[input] = res
            return res
        
        def diffWaysToCompute(self, input):
            """
            :type input: str
            :rtype: List[int]
            """
            dp = {}
            res = self.dpHelper(input, dp)
            return res
    

Log in to reply
 

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