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
The best I can work out so far, Python DP O(N*m*n), super slow still



@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_zerocount['0']][avail_onecount['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_zerozero_count][available_oneone_count] + 1 ].max end end end solutions[m][n] end
