Simple and space saving solution


  • 0
    S

    Using top down strategy to save some redundant logic and space complexity is O(nm)

    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            tmp = [[x.count('1'), x.count('0')] for x in strs]
            dp = [([0] * (m + 1)) for _ in xrange(n + 1)]
    
            for word_count in tmp:
                for i in xrange(n, word_count[0] - 1, -1):
                    for j in xrange(m, word_count[1] - 1, -1):
                        dp[i][j] = max(dp[i - word_count[0]][j - word_count[1]] + 1, dp[i][j])
            
            return dp[n][m]
    

Log in to reply
 

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