Time exceed, need optimize, need help :)


  • 0
    S

    I tried to used DP to solve the problem, but got time exceed for some test cases :( Can someone please give some suggestion about how I should optimize the code? Thanks

    class Solution(object):
        def maxNumber(self, nums1, nums2, k):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :type k: int
            :rtype: List[int]
            """
            dic = {}
            ary = []
            nums1, nums2 = tuple(nums1),tuple(nums2) 
            return self.recursive(dic,nums1, nums2, k)
            
        def recursive(self, dic, nums1, nums2, k):
            if not nums1 and not nums2: 
                dic[(nums1, nums2, k)] = []
                return dic[(nums1, nums2, k)]
            if k==1:
                dic[(nums1, nums2, k)] = [max(nums1+nums2)]
                return dic[(nums1, nums2, k)]
                
            if (nums1, nums2, k) in dic: return dic[(nums1, nums2, k)]
            
            val1 = -float('inf')
            tmpAry = []
            for idx1 in range(0,len(nums1)):
                if len(nums1[idx1:]+nums2)<k-1: break 
                ary1 = [nums1[idx1]]+self.recursive(dic, nums1[idx1+1:], nums2, k-1)
                val1 = max (val1, self.genDigit(ary1)) if len(tmpAry)<= len(ary1) else val1 
                if val1 == self.genDigit(ary1) and len(tmpAry)<= len(ary1):
                    tmpAry = ary1
            ary1 = tmpAry
            
            
            val2 = -float('inf')
            tmpAry2 = []
            for idx2 in range(0,len(nums2)):
                if len(nums1+nums2[idx2:])<k-1: break 
                ary2 = [nums2[idx2]]+self.recursive(dic, nums1, nums2[idx2+1:], k-1)
                val2 = max (val2, self.genDigit(ary2)) if len(tmpAry2)<= len(ary2) else val2
                if val2 == self.genDigit(ary2) and len(tmpAry2)<= len(ary2):
                    tmpAry2 = ary2
            ary2 = tmpAry2
            
            dic [(nums1, nums2, k)] = ary1 if self.genDigit(ary1) > self.genDigit(ary2) else ary2 
            return dic [(nums1, nums2, k)]
                    
        def genDigit(self, ary):
            return -float('inf') if not ary else int(reduce(lambda x,y : x+str(y), ary, ''))
    

Log in to reply
 

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