LeetCode Solutions
474. Ones and Zeroes
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// dp[i][j] := max size of the subset given i 0's and j 1's are available
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (const string& s : strs) {
const int count0 = count(begin(s), end(s), '0');
const int count1 = s.length() - count0;
for (int i = m; i >= count0; --i)
for (int j = n; j >= count1; --j)
dp[i][j] = max(dp[i][j], dp[i - count0][j - count1] + 1);
}
return dp[m][n];
}
};
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// dp[i][j] := max size of the subset given i 0's and j 1's are available
int[][] dp = new int[m + 1][n + 1];
for (final String s : strs) {
final int count0 = (int) s.chars().filter(c -> c == '0').count();
final int count1 = (int) s.length() - count0;
for (int i = m; i >= count0; --i)
for (int j = n; j >= count1; --j)
dp[i][j] = Math.max(dp[i][j], dp[i - count0][j - count1] + 1);
}
return dp[m][n];
}
}
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# dp[i][j] := max size of the subset given i 0's and j 1's are available
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
count0 = s.count('0')
count1 = len(s) - count0
for i in range(m, count0 - 1, -1):
for j in range(n, count1 - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - count0][j - count1] + 1)
return dp[m][n]