LC474. Ones and Zeroes
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.
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
求解利用m, n个0，1最多能构成给定序列里的多少个字符串。DP解法，dp{i}{j}代表利用i个0和j个1能构成的最多的String数量。
public class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// dp solution - dp[i][j] means max number of string composed with i 0s and j 1s
// dp[i][j] = max(dp[][])
int[][] dp = new int[m+1][n+1];
for(String str: strs){
int[] count = count(str);
for(int i = m; i >= count[0]; i--){
for(int j = n; j >= count[1]; j--){
dp[i][j] = Math.max(dp[i][j], dp[i-count[0]][j-count[1]]+1);
}
}
}
return dp[m][n];
}
private int[] count(String s){
char[] arr = s.toCharArray();
int[] res = new int[2];
for(char c: arr) res[c - '0']++;
return res;
}
}
O(kl + kmn), where k is the length of input string array and l is the average length of a string within the array.