4 Python solution with detailed explanation


  • 3
    G

    Solution

    Ones and Zeroes https://leetcode.com/problems/ones-and-zeroes/

    BruteForce

    • The recursion tree for this problem indicates that there are three states: i, m, and n. i refers to the start index for strs and m, n are the number of zeroes and ones allowed. The tree will perform a DFS like traversal for every possible start index i and record the number of strings that could be formed. The solution would be the maximum between all the initial start states.
    • The helper method takes m, n, and i as the parameters for this problem. Note we do not have any explicit checks like m ==0 and n==0 for a solution. m could be 0 and n could be non zero and subsequent items might just have 1s. Once we pick a candidate, we just check if we have sufficient zeroes and ones to accomodate it. If yes, we include it and make the next call.
    class Solution(object):
        def helper(self, strs, m, n, i):
            max_so_far = 0
            for idx in range(i, len(strs)):
                zeroes, ones = strs[idx].count('0'), strs[idx].count('1') 
                if m >= zeroes and n >= ones:
                    max_so_far = max(max_so_far, self.helper(strs, m-zeroes, n-ones, idx+1)+1)
            return max_so_far
        
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            cache = {}
            return self.helper(strs, m, n, 0)
    

    Memoization: O(MNL). TLE error

    • Find the maximum strings which can be created using m zeroes and n ones starting from index i in strs and store the results in a three dimensional table. The answer to the problem is then table[m,n,0]
    • The code is exactly like the brute force approach with an addition of a table.
    • This gives a TLE.
    class Solution(object):
        def helper(self, strs, m, n, i, table):
            if m in table and n in table[m] and i in table[m][n]:
                return table[m][n][i]
            table.setdefault(m, {}).setdefault(n, {})[i] = 0
            for idx in range(i, len(strs)):
                zeroes, ones = strs[idx].count('0'), strs[idx].count('1') 
                if m >= zeroes and n >= ones:
                    table[m][n][i] = max(table[m][n][i], self.helper(strs, m-zeroes, n-ones, idx+1, table)+1)
            return table[m][n][i]
        
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            return self.helper(strs, m, n, 0, {})
    

    Dynamic Programming: Time and Space O(MNL). MLE error

    • Find the maximum strings which can be created using m zeroes and n ones using indices 0 to i in strs (strs[0:i+1]) and store the results in a three dimensional table. The answer to the problem is then table[m,n,i]
    • For simplicity, we will parameterize i as the number of strings being used in strs so that we dont need to deal with negative indices.
    • Iterate from index 1 to len(strs). For a given index, we test all possible pairs of m and n.
    • If for a pair we find we have sufficient zeroes and ones to use str[i], we update table[i,j,k] as the max of table[i-1,j, k], 1+table[i-1,j-zeroes,k-ones]. This means that we are trying to find the maximum by either including it or not including it. For the case of inclusion, we need to find the maximum string we can until index i-1 with j-zeroes and k-ones.
    • If for a pair we find we do not have sufficient zeroes and ones, we update table[i,j,k] as table[i-1,j,k].
    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            table = {k:[[0]*(n+1) for _ in range(m+1)] for k in range(len(strs)+1)}
            for i in range(1, len(strs)+1):
                zeroes, ones = strs[i-1].count('0'), strs[i-1].count('1')
                for j in range(m+1):
                    for k in range(n+1):
                        if j >= zeroes and k >= ones:
                            table[i][j][k] = max(table[i-1][j][k], 1+table[i-1][j-zeroes][k-ones])
                        else:
                            table[i][j][k] = table[i-1][j][k]
            return table[len(strs)][m][n]
    

    *Dynamic Programming: Time O(MNL) and Space O(MN). Accepted Solution

    • Do we really need a three dimensional table? Process index i only requires the table for index i-1.
    • We can therefore use a prev and current table and achieve space complexity of O(MN).
    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            prev, curr = [[0]*(n+1) for _ in range(m+1)], [[0]*(n+1) for _ in range(m+1)]
            for i in range(1, len(strs)+1):
                zeroes, ones = strs[i-1].count('0'), strs[i-1].count('1')
                for j in range(m+1):
                    for k in range(n+1):
                        curr[j][k] = 0
                        if j >= zeroes and k >= ones:
                            curr[j][k] = max(prev[j][k], 1+prev[j-zeroes][k-ones])
                        else:
                            curr[j][k] = prev[j][k]
                prev, curr = curr, prev
            return prev[m][n]
    

Log in to reply
 

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