474. Ones and Zeroes

Question

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Solution 1

0-1背包问题的升级版。经典的背包问题只有一种容量，而这个问题实际等于有两种容量。

经典背包问题需要用二维数组动态规划，分别为物品和容量。
而这道题需要用三维数组动态规划，分别为字符串，0的容量和1的容量。

我们采用一个三维数组dp[i][j][k]保存可取最多物品的数量。
对于每个物品i，我们都可以取（数量+1）或不取（保持上一个物品的状态）。
j和k相当于分别记录了取“0”的总数和“1”的总数

遍历三个维度，并计算字符串中0和1的个数。

• 如果当总容量大于当前物品中zeros和ones的数量，则可以取当前的物品。

  • 如果取当前的物品，则dp[]数组的总数等于上一个物品的状态加一，即dp[i-1][j-zeros][k-ones]。
  • 也可以不取当前的物品，则dp[]数组的总数直接保持上一个物品的状态。

• 如果当前背包总容量小于zeros和ones的数量，则不能取当前物品。

  • 数组dp[]保持上一个物品的状态。

时间复杂度：O(lmn + L)，L是数组中所有字符串长度之和。
空间复杂度：O(lmn)。

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        
        for(int i = 1; i <= strs.length; i++){
            int zeros = 0, ones = 0;
            for(char c : strs[i-1].toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j - zeros >= 0 && k - ones >=0) dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
                    else dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        return dp[strs.length][m][n];
    }
}

Solution 2

由于dp[i][][]的上一个状态只涉及到dp[i-1][][]，因此我们可以采用滚动数组，去掉数组的一个维度，压缩空间。
此时需要从m到zeros，从n到ones倒序遍历，保证dp[i][][]转移过来的是dp[i-1][][]的元素。

此时的空间复杂度降低为O(mn)。

Code

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        
        for(String s : strs){   //记录每个位置对应的0和1数量
            int zeros = 0, ones = 0;
            for(char c : s.toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int i = m; i >= zeros; i--){
                for(int j = n; j >= ones; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

Solution 3

递归+记忆化搜索，保存并返回每个位置的最大长度。
如果位置越界则返回0。
如果memo[i][zero][one]不为0，则返回memo[i][zero][one]。

如果当前字符串的“0”和“1”的个数大于剩余的“0”和“1”的个数，则可以取当前字符串，递归下一个位置并加一。
也可以不取当前的字符串，递归下一个位置。当前位置memo[i][zero][one]等于两者中的最大值。

否则无法取当前字符串，直接递归下一个位置。当前位置等于0。

Code

class Solution {
    String[] s;
    int[] zeros, ones;
    int[][][] memo;
    public int findMaxForm(String[] strs, int m, int n) {
        s = strs;
        zeros = new int[strs.length];
        ones = new int[strs.length];
        memo = new int[strs.length][m+1][n+1];
        
        for(int i = 0; i < strs.length; i++){   //记录每个位置对应的0和1数量
            for(int j = 0; j < strs[i].length(); j++){
                if(s[i].charAt(j) == '0') zeros[i]++;
                else ones[i]++;
            }
        }
        return dfs(0, m, n);
    }
    
    private int dfs(int i, int zero, int one){
        if(i >= s.length){
            return 0;
        }
        if(memo[i][zero][one] != 0) return memo[i][zero][one];
        
        int maxPossibleSubset = 0;
        
        if(zero-zeros[i] >= 0 && one-ones[i] >= 0){
            maxPossibleSubset = 1 + dfs(i+1, zero-zeros[i], one-ones[i]);
        }
        memo[i][zero][one] = Math.max(maxPossibleSubset, dfs(i+1, zero, one));
        return memo[i][zero][one];
        
    }
}