Please increase the time limit for this problem


  • 0
    I

    Below is the top down python DP approach I came up with. It passes 57/60 test cases, and then gets TLE. I believe this approach is sufficient for an interview, and as such it should work for the OJ as well. Can the admin please at least slightly increase the time limit?
    I did not make any 3d array cause I thought that would be very annoying to code, so I just used a hashmap

        def can_make(self, m, n, string):
            return m >= string[0] and n >= string[1]
        
        def calc_max_strings(self, m, n, i, memo, strs):
            if i == 0:
                if self.can_make(m, n, strs[0]):
                    return 1
                return 0
            
            if (m,n,i) in memo:
                return memo[(m,n,i)]
                
            #choose to exclude i
            memo[(m,n,i)] = self.calc_max_strings(m, n, i-1, memo, strs)
            if self.can_make(m, n, strs[i]):
                create_i_max_strs = 1+self.calc_max_strings(m-strs[i][0], n-strs[i][1], i-1, memo, strs)
                memo[(m,n,i)] = max(memo[(m,n,i)], create_i_max_strs)
                
            return memo[(m,n,i)]
        
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            max_strings_memo = {}
            counted_strs = [None] * len(strs)
            for i in xrange(len(strs)):
                zero_cnt = 0
                one_cnt = 0
                for j in xrange(len(strs[i])):
                    if strs[i][j] == "0":
                        zero_cnt += 1
                    else:
                        one_cnt += 1
                        
                counted_strs[i] = [zero_cnt, one_cnt]
            
            return self.calc_max_strings(m, n, len(strs) - 1, max_strings_memo, counted_strs)

Log in to reply
 

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