Given an array, strs, with strings consisting of only 0s and 1s. Also two integers m and n.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Example 1:
Input:strs = ["10","0001","111001","1","0"], m = 5, n = 3Output:4Explanation:This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0".
Example 2:
Input:strs = ["10","0","1"], m = 1, n = 1Output:2Explanation:You could form "10", but then you'd have nothing left. Better form "0" and "1".
Constraints:
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] consists only of digits '0' and '1'.
1 <= m, n <= 100
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if (strs.length == 0) return 0;
int[][] f = new int[m + 1][n + 1];
for (int i = 1; i <= strs.length; i++) {
int ones = 0, zeros;
for (int j = 0; j < strs[i - 1].length(); j++) {
if (strs[i - 1].charAt(j) == '1') ones++;
}
zeros = strs[i - 1].length() - ones;
for (int j = m; j >= zeros; j--) {
for (int k = n; k >= ones; k--) {
f[j][k] = Math.max(f[j][k], f[j - zeros][k - ones] + 1);
}
}
}
return f[m][n];
}
}
网友评论