Ones and Zeroes
474. Ones and Zeroes
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m0s and n1s respectively. On the other hand, there is an array with strings consisting of only 0sand 1s.
Now your task is to find the maximum number of strings that you can form with given m0s and n1s. Each 0 and 1 can be used at mostonce.
Note:
- The given numbers of 0s and 1s will both not exceed 100
- The size of given string array won’t exceed 600.
Example 1:
|
1 2 3 4 5 |
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” |
Example 2:
|
1 2 3 4 5 |
Input: Array = {"10", "0", "1"}, m = 1, n = 1 Output: 2 Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1". |
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
public class Solution { public int findMaxForm(String[] strs, int m, int n) { //dp[m][n][i] = max(dp[m][n][i - 1] , dp[m - one[i]][n - zero[i]][i - 1] + 1) // dp[m][n] = max(dp[m - one[i]][n-zero[i]] + 1, dp[m][n]) int[][] dp = new int[m + 1][n + 1]; // no need to initialize for(int i = 0; i < strs.length; i++) { int[] oneZero = new int[2]; cnt(strs[i], oneZero); if(oneZero[0] <= m && oneZero[1] <= n) { for(int mi = oneZero[0]; mi <= m; mi++) { for(int nj = oneZero[1]; nj <= n; nj++) { // it is wrong to do initialize here //dp[mi][nj] = 1; ; } } } } for(int i = 0; i < strs.length; i++) { int[] cnt = new int[2]; cnt(strs[i], cnt); for(int mi = m; mi >= cnt[0]; mi--) { for(int nj = n; nj >= cnt[1]; nj--) { dp[mi][nj] = Math.max(dp[mi][nj], dp[mi - cnt[0]][nj - cnt[1]] + 1); } } } return dp[m][n]; } void cnt(String s, int[] oneZero) { for(char c: s.toCharArray()) { if(c == '0') { oneZero[0]++; } else if(c == '1') { oneZero[1]++; } } } } |
DFS:
|
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 27 28 29 30 31 32 33 34 |
public class Solution { public int findMaxForm(String[] strs, int m, int n) { int[] res = new int[1]; dfs(strs, 0, m, n, 0, res); return res[0]; } void dfs(String[] strs, int index, int zeroNum, int oneNum, int wordsCnt, int[] res) { if(index == strs.length) { res[0] = Math.max(wordsCnt, res[0]); return; } String s = strs[index]; int[] cnt = cnt(s); // use current string if(cnt[0] <= zeroNum && cnt[1] <= oneNum) { dfs(strs, index + 1, zeroNum - cnt[0], oneNum - cnt[1], wordsCnt + 1, res); } // not use current string dfs(strs, index + 1, zeroNum, oneNum, wordsCnt, res); } int[] cnt(String s) { int[] res = new int[2]; for(char c: s.toCharArray()) { if(c == '0'){ res[0]++; } else if(c == '1') { res[1]++; } } return res; } } |
