474.ones-and-zeros-cn

题目地址

https://leetcode.com/problems/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 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 and 1s will both not exceed 100
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".

思路

题意是给定一个只包含0 和 1 的字符串数组, 求在字符串数组中最多能用m个0和n和1能组成多少个字符串。

一般看到这种要求最多，最大个数，但不需要列举出所有情况的题，很大概率会用到DP求解。而且这是一道很典型的 0-1背包问题，对于当前字符串，要么取，要么不取的问题。

因为面试过程中，由于各种原因，可能不会立马想到DP解，这里我们先从暴力解开始分析，一步步优化，最后得出最优解，面试很重视的一个过程，

解法一 - 暴力解

暴力解就是非常暴力的列举出所有字符串数组的子集，然后计算每个子集的 0和1 的个数，并用一个全局变量max表示最多，如果计算出子集中0 和 1 个数小于等于给定的m 和 n，即 count(0) <= m && count(1) <= n;.

给定长度为len的字符串数组，总共有2^len个子集。时间复杂度太高。

复杂度分析

• 时间复杂度: O(2^len * s) - len is Strs length, s is the average string length

• 空间复杂度: O(1)

解法二 - 记忆 + 递归

上面暴力解递归实现的方法中，暴力解求解了所有的子集，我们可以用一个memory数组记录下已经求解过的子集，如果碰到相同的则直接从memory中取，不用再求解。

memo[i][j][k] - 表示前i个字符串中能用j个0和k和1组成的最多的字符串个数。

用helpe(strs, i, j, k, memo) 递归求解： 1. 如果memo[i][j][k] != 0, 表示已经求解过了，所以直接返回值即可 2. 如果没有求解过，判断当前剩余的0和1的个数j和k是否大于等于当前字符串的0和1的个数， a. 满足条件，则可以取当前字符串， 3. 不取当前字符串。 4. 取最大值保存在memo[i][j][k]

复杂度分析

• 时间复杂度: O(l * m * n) - l 是字符串数组的长度，m是0的个数，n是1的个数

• 空间复杂度: O(l * m * n) - memo 三维数组

解法三 - 三维DP

解法二中用了记忆和递归，那么也可以用迭代的方式即三维DP求解。

dp[i][j][k] - 表示前i个字符串中能用j个0和k和1组成的最多的字符串个数。

状态转移方程： dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - count0][k - count1]) - count0 和 count1 分别表示第 i 个字符串（strs[i]) 中 0 的个数 和 1 的个数`

根据 j，k 与 count0和 count1 比较，取与不取当前的字符串，最终状态转移方程：

• j >= count0 && k >= count1,

  dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - count0][k - count1] + 1)

• 不满条件，不取当前字符串

  dp[i][j][k] = dp[i - 1][j][k]

最后dp[l][m][n] 即可得到最大值。

复杂度分析

• 时间复杂度: O(l * m * n) - l 是字符串数组的长度，m是0的个数，n是1的个数

• 空间复杂度: O(l * m * n) - dp 三维数组

解法四 - 二维DP

解法三中，分析三维DP，对于每次计算，我们并不需要所有状态的值，只需要前一行的状态值即（i-1）所有可以优化空间从l -> 2 即dp[2][m][n], 再进一步分析可以发现，其实并不需要前一行中所有状态，这里只需要记录两个位置的状态， 即dp[i - 1][j][k] 和 dp[i - 1][j - count0][k - count1]。 那么就可以降维到二维DP，

状态转移方程：

dp[i][j] = max(dp[i][j], dp[i - count0][j - count1] + 1)

如图举例：

ones and zeros 2d dp

复杂度分析

• 时间复杂度: O(l * m * n) - l 是字符串数组的长度，m是0的个数，n是1的个数

• 空间复杂度: O(m * n) - dp 三维数组

关键点分析

代码 (Java/Python3)

解法一 - 递归 (超时)

Java code

class OnesAndZerosBFRecursive {
 public int findMaxForm2(String[] strs, int m, int n) {
    return helper(strs, 0, m, n);
 }
 private int helper(String[] strs, int idx, int j, int k) {
    if (idx == strs.length) return 0;
    // count current idx string number of zeros and ones
    int[] counts = countZeroOnes(strs[idx]);
    // if j >= count0 && k >= count1, take current index string
    int takeCurrStr = j - counts[0] >= 0 && k - counts[1] >= 0
        ? 1 + helper(strs, idx + 1, j - counts[0], k - counts[1])
        : -1;
    // don't take current index string strs[idx], continue next string
    int notTakeCurrStr = helper(strs, idx + 1, j, k);
    return Math.max(takeCurrStr, notTakeCurrStr);
 }
 private int[] countZeroOnes(String s) {
    int[] res = new int[2];
    for (char ch : s.toCharArray()) {
      res[ch - '0']++;
    }
    return res;
 }
}

Python3 code

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        return self.helper(strs, m, n, 0)

    def helper(self, strs, m, n, idx):
        if idx == len(strs):
            return 0
        take_curr_str = -1
        count0, count1 = strs[idx].count('0'), strs[idx].count('1')
        if m >= count0 and n >= count1:
            take_curr_str = max(take_curr_str, self.helper(strs, m - count0, n - count1, idx + 1) + 1)
        not_take_curr_str = self.helper(strs, m, n, idx + 1)
        return max(take_curr_str, not_take_curr_str)

解法二 - 记忆 + 递归

Java code

class OnesAndZerosMemoRecur {
  public int findMaxForm4(String[] strs, int m, int n) {
      return helper(strs, 0, m, n, new int[strs.length][m + 1][n + 1]);
  }
  private int helper(String[] strs, int idx, int j, int k, int[][][] memo) {
      if (idx == strs.length) return 0;
      // check if already calculated, return value
      if (memo[idx][j][k] != 0) {
        return memo[idx][j][k];
      }
      int[] counts = countZeroOnes(strs[idx]);
      // if satisfy condition, take current string, strs[idx], update count0 and count1
      int takeCurrStr = j - counts[0] >= 0 && k - counts[1] >= 0
          ? 1 + helper(strs, idx + 1, j - counts[0], k - counts[1], memo)
          : -1;
      // not take current string
      int notTakeCurrStr = helper(strs, idx + 1, j, k, memo);
      // always keep track the max value into memory
      memo[idx][j][k] = Math.max(takeCurrStr, notTakeCurrStr);
      return memo[idx][j][k];
  }
  private int[] countZeroOnes(String s) {
       int[] res = new int[2];
       for (char ch : s.toCharArray()) {
         res[ch - '0']++;
       }
       return res;
  }
}

Python3 code - (TLE)

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        memo = {k:[[0]*(n+1) for _ in range(m+1)] for k in range(len(strs)+1)}
        return self.helper(strs, 0, m, n, memo)

    def helper(self, strs, idx, m, n, memo):
        if idx == len(strs):
            return 0
        if memo[idx][m][n] != 0:
            return memo[idx][m][n]
        take_curr_str = -1
        count0, count1 = strs[idx].count('0'), strs[idx].count('1')
        if m >= count0 and n >= count1:
            take_curr_str = max(take_curr_str, self.helper(strs, idx + 1, m - count0, n - count1, memo) + 1)
        not_take_curr_str = self.helper(strs, idx + 1, m, n, memo)
        memo[idx][m][n] = max(take_curr_str, not_take_curr_str)
        return memo[idx][m][n]

解法三 - 3D DP

Java code

class OnesAndZeros3DDP {
  public int findMaxForm(String[] strs, int m, int n) {
      int l = strs.length;
      int [][][] d = new int[l + 1][m + 1][n + 1];
      for (int i = 0; i <= l; i ++){
        int [] nums = new int[]{0,0};
        if (i > 0){
          nums = countZeroOnes(strs[i - 1]);
        }
        for (int j = 0; j <= m; j ++){
          for (int k = 0; k <= n; k ++){
            if (i == 0) {
              d[i][j][k] = 0;
            } else if (j >= nums[0] && k >= nums[1]){
              d[i][j][k] = Math.max(d[i - 1][j][k], d[i - 1][j - nums[0]][k - nums[1]] + 1);
            } else {
              d[i][j][k] = d[i - 1][j][k];
            }
          }
        }
      }
      return d[l][m][n];
  }
}

解法四 - 2D DP

Java code

class OnesAndZeros2DDP {
  public int findMaxForm(String[] strs, int m, int n) {
      int[][] dp = new int[m + 1][n + 1];
      for (String s : strs) {
        int[] counts = countZeroOnes(s);
        for (int i = m; i >= counts[0]; i--) {
          for (int j = n; j >= counts[1]; j--) {
            dp[i][j] = Math.max(1 + dp[i - counts[0]][j - counts[1]], dp[i][j]);
          }
        }
      }
      return dp[m][n];
  }
  private int[] countZeroOnes(String s) {
       int[] res = new int[2];
       for (char ch : s.toCharArray()) {
         res[ch - '0']++;
       }
       return res;
  }
}

Python3 code

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

相似题

• Leetcode 600. Non-negative Integers without Consecutive Ones

• Leetcode 322. Coin Change