# Accepted Python solution (102ms)

• Idea is to use DP only over 'ones' dimension. Optimal strategy for consuming 'zeros' is achieved by sorting list of strings by number of zeroes.

``````def findMaxForm(self, strs, m, n):
if not strs:
return 0

# Convert strings to list of (#zeroes, #ones) pairs
nums = [(s.count('0'), s.count('1')) for s in strs]
nums.sort()
if nums[0][0] > m:
return 0

# A[i][j] = Tuple (max formed strings, min used zeroes) in
# examined first i strings and used j ones.
A = []
for i in range(len(strs) + 1):
A.append([(0, 0)] * (n + 1))

for i, (z, o) in enumerate(nums):
for j in range(0, n + 1):
# We just skip this string
A[i + 1][j] = A[i][j]
if j - o >= 0:
(count, zz) = A[i][j - o]
# We use the string if the usage of zeroes
# is under limits and number of formed
# strings can be increased.
if zz + z <= m and A[i + 1][j][0] < 1 + count:
A[i + 1][j] = (1 + count, zz + z)
return A[len(strs)][n][0]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.