The best I can work out so far, Python DP O(N*m*n), super slow still

• ``````class Solution(object):
def findMaxForm(self, strs, m, n):
dic0, dic1 = {}, {}
for i in xrange(len(strs)):
dic0[i] = strs[i].count('0')
dic1[i] = len(strs[i]) - dic0[i]
ans = 0
maxPair = {(0, 0): [0, 0]}
for i in xrange(len(strs)):
for j in xrange(m + 1):
for l in xrange(n + 1):
if j >= dic0[i] and l >= dic1[i] and (j - dic0[i], l - dic1[i]) in maxPair and maxPair[(j - dic0[i], l - dic1[i])][1] != i + 1:
if maxPair[(j - dic0[i], l - dic1[i])][0] + 1 > maxPair.get((j, l), [0, 0])[0]:
maxPair[(j, l)] = [maxPair[(j - dic0[i],l - dic1[i])][0] + 1, i + 1]
ans = max(ans, maxPair[ (j, l) ][0])
return ans
``````

• @Ipeq1 I have increased the time limit, your solution is now accepted.

• @1337c0d3r Thank you, the Boss! :) BTW, am I on the right track with this problem? Not sure if it's normal that my "AC" solution runs so slowly...

• @1337c0d3r Could you also take a look at Ruby? I implemented the same algorithm in both Python and Ruby. Only the Python one get accepted.

Python

``````from collections import defaultdict

class Solution(object):
def findMaxForm(self, strs, m, n):
# solutions is a (m+1)x(n+1) matrix
solutions = [ [0] * (n+1) for _ in xrange(m+1) ]

for string in strs:

count = defaultdict(int)
for c in string:
count[c] += 1

for avail_zero in xrange(m, count['0']-1, -1):
for avail_one in xrange(n, count['1']-1, -1):
solutions[avail_zero][avail_one] = max(
solutions[avail_zero][avail_one],
solutions[avail_zero-count['0']][avail_one-count['1']] + 1
)

return solutions[m][n]
``````

Ruby

``````def find_max_form(strs, m, n)
solutions = (m+1).times.map { [0] * (n+1) }

strs.each do |str|
zero_count = str.count('0')
one_count = str.count('1')
m.downto(zero_count).each do |available_zero|
n.downto(one_count).each do |available_one|
solutions[available_zero][available_one] = [
solutions[available_zero][available_one],
solutions[available_zero-zero_count][available_one-one_count] + 1
].max
end
end
end

solutions[m][n]
end
``````

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