Python DFS with Cache beats 99%


  • 0
    A
    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """        
            cache = {}
            return self.dfs(sorted(strs, key=lambda x: (-len(x), x)), 0, m, n, cache)
        def dfs(self, strs, index, m, n, cache):
            if index == len(strs) or (m == 0 and n == 0):
                return 0
            if (index, m, n) in cache:
                return cache[(index, m, n)]
            res = 0
            for i in xrange(index, len(strs)):
                if i > index and strs[i] == strs[i-1]:
                    continue
                curr = strs[i]
                z, o = curr.count('0'), curr.count('1')
                if m - z < 0 or n - o < 0:
                    continue
                res = max(self.dfs(strs, i+1, m - z, n - o, cache) + 1, res)  
            cache[(index, m, n)] = res
            return res

Log in to reply
 

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