LeetCode 474. Ones and Zeroes

December 13, 2020

mediumLeetCode

This reduces to a knapsack problem where:

$w_i = (x,y)$ where $x$ = #0s, $y$ = #1s

$W = (m,n)$

We can build a matrix, $dp$ , where $dp[i][j] =$ the maximum # of items we can fit in the weight constraint $(i,j)$ .

We can add items, $w_i$ , to the matrix one by one. At each step, $dp$ contains the maximum from the first $i$ items.

After adding every item, our answer is the maximum # of items that we can fit in $W$ , or $dp[m][n]$ .

This algorithm runs in psuedo-polynomial $O(mns)$ time, where $s =$ the sum of lengths of all the input strings.

from typing import Dict, List, Set, Tuple
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.findMaxForm(["10","0001","111001","1","0"], 5, 3), 4)
        self.assertEqual(self.s.findMaxForm(["10","0","1"], 1, 1), 2)

    def test_empty(self):
        self.assertEqual(self.s.findMaxForm([], 1, 1), 0)

    def test_long(self):
        self.assertEqual(self.s.findMaxForm(["0","11","1000","01","0","101","1","1","1","0","0","0","0","1","0","0110101","0","11","01","00","01111","0011","1","1000","0","11101","1","0","10","0111"], 9, 80), 17)

class Solution:

    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n+1) for _ in range(m+1)]
        items = [(s.count("0"), s.count("1")) for s in strs]
        for wi,wj in items:
            for i in range(m, wi-1, -1):
                for j in range(n, wj-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-wi][j-wj]+1)
        return dp[m][n]

if __name__ == "__main__":
    unittest.main()