equivalent to the results[][][]equivalOnes and Zeroes

Link: https://leetcode.com/problems/ones-and-zeroes/

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator ofm0sandn1srespectively. On the other hand, there is an array with strings consisting of only0sand1s.

Now your task is to find the maximum number of strings that you can form with givenm0sandn1s. Each0and1can be used at mostonce.

Note:

1. The given numbers of 0s and 1s will both not exceed 100
2. The size of given string array won't exceed 600

Example 1:

Input:
 Array = {"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:
 Array = {"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"

Solution: Knapsack Problem (0-1 Knapsack Problem):

class Solution(object):

    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        if m < 0 or n < 0:
            raise ValueError('m and n should be greater than or equal to 0')
        if not strs:
            return 0

        # init results
        results = [[0 for _ in xrange(n + 1)] for _ in xrange(m + 1)]

        for s in strs:
            num_of_zeros = sum([1 for c in s if c == '0'])
            num_of_ones = sum([1 for c in s if c == '1'])

            for j in xrange(m, -1, -1):
                for k in xrange(n, -1, -1):
                    if num_of_zeros <= j and num_of_ones <= k:
                        results[j][k] = max(results[j][k],
                                            results[j - num_of_zeros][k - num_of_ones] + 1)

        return results[m][n]

class Solution(object):

    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        if m < 0 or n < 0:
            raise ValueError('m and n should be greater than or equal to 0')
        if not strs:
            return 0

        # init results
        results = [[[0 for _ in xrange(n + 1)] for _ in xrange(m + 1)] for _ in xrange(len(strs) + 1)]

        for i in xrange(1, len(strs) + 1):
            s = strs[i - 1]
            num_of_zeros = sum([1 for c in s if c == '0'])
            num_of_ones = sum([1 for c in s if c == '1'])

            for j in xrange(m + 1):
                for k in xrange(n + 1):
                    if num_of_zeros <= j and num_of_ones <= k:
                        results[i][j][k] = max(results[i - 1][j][k], 
                                               results[i - 1][j - num_of_zeros][k - num_of_ones] + 1)
                    else:
                        results[i][j][k] = results[i - 1][j][k]

        return results[len(strs)][m][n]

Note:

• In the second solution (which uses three dimensional matrix), we add 'if-else' in the most inner loop. Because when the current 'item' cannot fit the knapsack, we still need to assign the value the results[i][j][k], and because we cannot put the current 'item' into the 'bag', the max benefits for the results[i][j][k] is results[i - 1][j][k].
• The reason we don't need use 'if-else' in the most inner loop in the first solution is that if we don't update the results[j][k], the current results[j][k] is storing the previous row's results[j][k], which is equivalent to the results[i - 1][j][k].
• To avoid 'i - 1' is '-1', we using the 'len(strs) + 1' to initialize the results matrix's first dimension.

Time Limited Exceed

class Solution(object):
    def __init__(self):
        self.max_num_of_strs = 0

    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        if m < 0 or n < 0:
            raise ValueError('m and n should be greater than or equal to 0')
        if not strs:
            return 0

        result_set = set()    
        buff = []
        self.find_max_form_helper(strs, m, n, 0, buff, result_set)
        return self.max_num_of_strs

    def find_max_form_helper(self, strs, m, n, curr_index, buff, result_set):
        # base case
        if curr_index >= len(strs):
            return

        for i in xrange(curr_index, len(strs)):
            buff.append(strs[i])
            buff_str = ','.join(buff)

            if buff_str not in result_set:
                result_set.add(buff_str)
                if self.is_valid(buff, m, n):
                    self.max_num_of_strs = max(self.max_num_of_strs, len(buff))

                # recursion
                self.find_max_form_helper(strs, m, n, i + 1, buff, result_set)

            buff.pop()

    def is_valid(self, arr, m, n):
        for str in arr:
            m -= self.get_num_of_target_chars(str, '0')
            if m < 0:
                return False

            n -= self.get_num_of_target_chars(str, '1')
            if n < 0:
                return False

        return True

    def get_num_of_target_chars(self, str, target_char):
        counter = 0
        for c in str:
            if c == target_char:
                counter += 1

        return counter