[LeetCode] Ones and Zeroes

474. Ones and Zeroes

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

Return the size of the largest subset of strs 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
int dp[101][101];
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int res = 0;
memset(dp, 0, sizeof dp);
for(auto& str : strs) {
int zero = 0, one = 0;
for(auto& ch : str) {
if(ch == '0') zero++;
else one++;
}
if(zero > m or one > n) continue;
for(int i = m - zero; i >= 0; i--) {
for(int j = n - one; j >= 0; j--) {
dp[i+zero][j+one] = max(dp[i+zero][j+one], 1 + dp[i][j]);
res = max(res, dp[i+zero][j+one]);
}
}

dp[zero][one] = max(dp[zero][one], 1);
res = max(res, dp[zero][one]);
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/12/PS/LeetCode/ones-and-zeroes/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.