Medium

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10","0001","111001","1","0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10", "0001", "1", "0"}，因此答案是 4。
其他满足题意但较小的子集包括 {"0001", "1"} 和 {"10", "1", "0"}。
{"111001"} 不满足题意，因为它含有 4 个 1，大于 n 的值 3。

示例 2：

输入：strs = ["10","0","1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"}，所以答案是 2。

提示：

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由数字 '0' 和 '1' 组成
  • 1 <= m, n <= 100

解题思路

这是一道经典的二维背包问题。我们需要在有限的 0 和 1 的数量约束下，选择尽可能多的字符串。

思路分析：

  1. 状态定义：设 dp[i][j] 表示使用最多 i 个 0 和 j 个 1 能够得到的字符串的最大数量。

  2. 状态转移：对于每个字符串，统计其包含的 0 和 1 的个数，记为 zeros 和 ones。对于当前字符串，我们有两个选择：

    • 不选择当前字符串：dp[i][j] 保持不变
    • 选择当前字符串：dp[i][j] = dp[i-zeros][j-ones] + 1（前提是 i >= zeros 且 j >= ones）

  3. 优化空间：由于每个字符串只能使用一次，我们需要从后往前更新 dp 数组，避免重复使用同一个字符串。

  4. 初始化：dp[0][0] = 0，其他位置初始化为 0。

算法步骤：

  • 遍历每个字符串，统计其 0 和 1 的个数
  • 从后往前更新 dp 数组，确保每个字符串只被使用一次
  • 返回 dp[m][n] 作为最终答案

这种方法本质上是 0-1 背包问题的二维扩展，时间复杂度为 O(len × m × n)，空间复杂度为 O(m × n)。

代码实现

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (const string& str : strs) {
            int zeros = 0, ones = 0;
            for (char c : str) {
                if (c == '0') zeros++;
                else ones++;
            }
            
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        
        return dp[m][n];
    }
};

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for s in strs:
            zeros = s.count('0')
            ones = s.count('1')
            
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        
        return dp[m][n]

public class Solution {
    public int FindMaxForm(string[] strs, int m, int n) {
        int[,] dp = new int[m + 1, n + 1];
        
        foreach (string str in strs) {
            int zeros = 0, ones = 0;
            foreach (char c in str) {
                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];
    }
}

var findMaxForm = function(strs, m, n) {
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (const str of strs) {
        let zeros = 0, ones = 0;
        for (const char of str) {
            if (char === '0') zeros++;
            else ones++;
        }
        
        for (let i = m; i >= zeros; i--) {
            for (let j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    
    return dp[m][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(len × m × n)len 为字符串数组长度，需要遍历每个字符串并更新 dp 数组
空间复杂度O(m × n)需要一个二维 dp 数组存储状态

相关题目