# Time exceed, need optimize, need help :)

• 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, ''))

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