474 Ones and Zeroes

474. Ones and Zeroes

1. Question

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 m0sand n1srespectively. On the other hand, there is an array with strings consisting of only0sand1s.

Now your task is to find the maximum number of strings that you can form with givenm0sandn1s. Each0and1can be used at most once.

Note:

1. The given numbers of0sand1swill both not exceed100

2. The size of given string array won't exceed600.

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".

2. Implementation

(1) DP

思路: 这题要我们用m个0和n个1，组成最多的string(每个string都由0或1组成)。这是很明显的0-1背包问题，是二维的0-1背包问题，可以直接用模板写

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0 || m < 0 || n < 0) {
            return 0;
        }

        // dp[i][j][k] means the max number of strings we can form with number of j 0s and k 1s for the first i strings in strs
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int[] count = new int[2];

        for (int i = 0; i <= strs.length; i++) {
            // The first row is empty string, skip the first row
            if (i == 0) continue;

            count = countOnesAndZeroes(strs[i - 1]);

            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // When we have enough 1s and 0s to form the current string string strs[i - 1]
                    // Two strategies: Form it or skip it
                    if (count[0] <= j && count[1] <= k) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - count[0]][k - count[1]] + 1);
                    }
                    // Do nothing
                    else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

    public int[] countOnesAndZeroes(String s) {
        int[] count = new int[2];

        for (char c : s.toCharArray()) {
            ++count[c - '0'];
        }
        return count;
    }
}

(2) DP空间优化

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0|| m < 0 || n < 0) {
            return 0;
        }

        int[][] dp = new int[m + 1][n + 1];
        int[] count = new int[2];

        for (int i = 0; i < strs.length; i++) {
            count = countOnesAndZeroes(strs[i]);

            for (int j = m; j >= count[0]; j--) {
                for (int k = n; k >= count[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public int[] countOnesAndZeroes(String s) {
        int[] count = new int[2];

        for (char c :s.toCharArray()) {
            ++count[c - '0'];
        }
        return count;
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(k * l * m * n), 空间复杂度O(kmn)

DP空间优化: 时间复杂度O(k * l * m * n), 空间复杂度O(mn)