Leetcode 474. Ones and Zeroes
Given an array, strs, with strings consisting of only 0s and 1s. Also two integers m and n.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.
Example 1:
Input: strs = ["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: strs = ["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".
Constraints:
1 <= strs.length <= 600
1 <= strs.length <= 100
strs consists only of digits '0' and '1'.
1 <= m, n <= 100
class Solution:
def findMaxForm(self, strs: List, m: int, n: int) -> int:
N = len(strs)
dp = [ for _ in range(m + 1)]
for k in range(1, N + 1):
count_0 = 0
count_1 = 0
for c in strs:
if c == '0': count_0 += 1
if c == '1': count_1 += 1
for i in range(m, count_0 - 1, -1):
for j in range(n, count_1 - 1, -1):
dp = max(dp, dp + 1)
return dp
页:
[1]