474. Ones and Zeroes

LeetCode 474. Ones and Zeroes

Description

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset ofstrs such that there are at most m 0 ' s and n 1 ' s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

• 1 <= strs.length <= 600

• 1 <= strs[i].length <= 100

• strs[i] consists only of digits '0' and '1'.

• 1 <= m, n <= 100

Tags

Dynamic Programming

Solution

这道题和经典的背包问题很类似，不同之处体现在这道题有两种容量。用 dp(i, j) 表示容量为 i 个 0 和 j 个 1时集合的最大长度，那么状态转移方程为：

dp(i, j) = max(1 + dp(i - cost_0[k], j - cost_1[k])) if i >= cost_0[k] and j >= cost_1[k]

k代表第k个字符串，因此我们遍历每个字符串，统计他的cost_0和cost_1，从大到小进行枚举。最后返回dp[m][n]，表示两种容量分别为m和n时最大的集合长度。

This question is a variant of Knapsack problem, but the difference is that this problem has two types of capacities. We use dp(i, j) to represent the longest length when 0's capacity is i and 1's is j. We formulate the transform function as:

dp(i, j) = max(1 + dp(i - cost_0[k], j - cost_1[k])) if i >= cost_0[k] and j >= cost_1[k]

We denote k as the kth string, so we iterate over the string slice and count the number of 0 and 1, as cost_0 and cost_1 respectively, appearing in each string. Enumerate from high capacity to low. Finally, we return dp[m][n].

Complexity

• Time complexity: $O(mnl)$

• Space complexity: $O(mn)$

Code

func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for _, s := range strs {
		var n0, n1 int
		for _, c := range s {
			if c == '0' {
				n0++
			} else {
				n1++
			}
		}
		for i := m; i >= n0; i-- {
			for j := n; j >= n1; j-- {
				if v := 1 + dp[i-n0][j-n1]; dp[i][j] < v {
					dp[i][j] = v
				}
			}
		}
	}
	return dp[m][n]
}

Reference

1. 一和零