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


  • 0
    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
    

  • 1

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


  • 0

    @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...


  • 0

    @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
    

  • 0

Log in to reply
 

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