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; } };
|