In this Leetcode Ones and Zeroes problem solution 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.
Problem solution in Python.
from collections import Counter
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
weights = []
for st in strs:
counter = Counter(st)
weights.append((counter.get("0", 0), counter.get("1", 0)))
self.visited = {}
return self.recursiveWithMemo(strs, weights, len(strs) - 1, (m, n))
# Brute Force Recursive Solution
def recursiveWithoutMemo(self, strs, weights, index, wt):
if wt == (0, 0) or index < 0: return 0
else:
curr = weights[index]
if curr[0] <= wt[0] and curr[1] <= wt[1]:
return max(
1 + self.recursiveWithoutMemo(strs, weights, index - 1, (wt[0] - curr[0], wt[1] - curr[1])),
self.recursiveWithoutMemo(strs, weights, index - 1, wt)
)
else:
return self.recursiveWithoutMemo(strs, weights, index - 1, wt)
Problem solution in Java.
public int findMaxForm(String[] strs, int m, int n) {
Arrays.sort(strs, new Comparator<String>(){
public int compare(String s1, String s2) {
int val = s1.length() - s2.length();
if(val != 0)
return val;
return s1.compareTo(s2);
}
});
int result = 0;
for(int i = 0; i < strs.length; i++)
result = Math.max(result, dfs(strs, m, n, i));
return result;
}
public int dfs(String[] strs, int m, int n, int start) {
boolean flag;
int result = 0, mm, nn;
for(; start < strs.length; start++) {
char[] c = strs[start].toCharArray();
flag = true;
if(c.length > m + n)
break;
mm = m;
nn = n;
for(int i = 0; i < c.length; i++) {
if(c[i] == '0' && m > 0)
m--;
else if(c[i] == '1' && n > 0)
n--;
else {
flag = false;
break;
}
}
if(flag)
result++;
else {
m = mm;
n = nn;
}
}
return result;
}
Problem solution in C++.
pair<int, int> countChars(string& str) {
int ones = 0, zeros = 0;
for (auto c : str) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
return {zeros, ones};
}
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<vector<int>>> dp(strs.size() + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
for (int i = 0; i < strs.size(); i++) {
auto counts = countChars(strs[i]);
int ones = counts.second, zeros = counts.first;
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
if (zeros <= j && ones <= k) {
dp[i + 1][j][k] = max(dp[i][j][k], 1 + dp[i][j - zeros][k - ones]);
} else {
dp[i + 1][j][k] = dp[i][j][k];
}
}
}
}
return dp[strs.size()][m][n];
}
0 Comments