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 m
0s
and n 1s
respectively. On the other hand, there is an array with strings consisting of only 0s
and 1s
.
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.
Note:
- The given numbers of
0s
and1s
will both not exceed100
- The size of given string array won't exceed
600
.
Example 1:
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:
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".
Analysis:
This is a classic backpack DP problem. Use dp[m + 1][n + 1], where dp[i][j] denotes for number of i 1s and j 0s, the maximum number of strings.
Code (Java):
class Solution { public int findMaxForm(String[] strs, int m, int n) { if (strs == null || strs.length == 0) { return 0; } int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= strs.length; i++) { for (int j = m; j >= 0; j--) { for (int k = n; k >= 0; k--) { int num0 = 0; int num1 = 0; int[] count = countNumberOfZerosAndOnes(strs[i - 1]); num0 = count[0]; num1 = count[1]; // no pick // int noPick = dp[j][k]; // pick // int pick = 0; if (j - num0 >= 0 && k - num1 >= 0) { pick = dp[j - num0][k - num1] + 1; } dp[j][k] = Math.max(pick, noPick); } } } return dp[m][n]; } private int[] countNumberOfZerosAndOnes(String s) { int zero = 0; int one = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '0') { zero++; } else { one++; } } return new int[]{zero, one}; } }
No comments:
Post a Comment