7-line DP solution time O(m*n*strs.length) (detailed explanation)


  • 0
        int findMaxForm(vector<string>& strs, int n0, int n1) {
          vector<vector<int>> dp(n0+1, vector<int>(n1+1)); // dp[i][j] = results if using i 0's and j 1's 
          for (auto &s : strs) {
            vector<int> freq(2); for (char c : s) ++freq[c-'0']; // 0's and 1's frequency in s
            for (int num0 = n0; num0 >= freq[0]; --num0)
        	for (int num1 = n1; num1 >= freq[1]; --num1)
              dp[num0][num1] = max(dp[num0][num1], 1 + dp[num0 - freq[0]][num1 - freq[1]]);
          }
          return dp[n0][n1];
        }
    

    Key observation: Let dp(n0, n1, k) be the max number of strings which could be formed by using n0 0's and n1 1's in the first k strings of the given string array, then we have

    • initial condition: dp(n0, n1, 0) = 0 for any n0, n1,
    • boundary condition: dp(n0, n1, k) = 0 for any n0 < 0 or n1 < 0,
    • recursion: dp(n0, n1, k) = max( dp(n0, n1, k-1), 1+dp(n0-freq[k-1][0], n1-freq[k-1][1], k-1) ),

    where freq[k-1][0], freq[k-1][1] are frequencies of char '0' and '1' in the kth string.

    The recursion means that if we try to form first k strings with n0 0's and n1 1's, there are only two cases:

    1. The kth string is not formed, so the max number of formed strings is same as using only first k-1 strings;
    2. Otherwise, we have used freq[k-1][0] 0's and freq[k-1][1] 1's to form the kth string, and so with n0 - freq[k-1][0] 0's and n1 - freq[k-1][1] 1's left to form first k-1 strings.

    The result of dp(n0, n1, k) is whichever case 1 and case 2 has the larger number of strings formed.



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