3 solutions(256ms for dp and 13ms for greedy) for reference


  • 0
    S

    For this problem, BF may be one way to work out, that is list all sub sets and count the number that can satisfy m and n. However, O(2^N) it is toooooooooo slow.

    Then we come to dp, there are three variables in this problem, so we can define dp[k][i][j] as the max number of the front k strings with i 0s and j 1s.
    And then we can get:
    dp[k][i][j] = max(max(dp[k][i][j], dp[k-1][i-zero][j-one] + 1), dp[k-1][i][j]), // zero/one is the number of 0s/1s of string[k-1], i >= zero and j >= one.
    if i<zero or j < one, just put the previous one: dp[k][i][j] = dp[k-1][i][j];

    then code is as follows:

    class Solution {
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
            vector<vector<vector<int>>> dp(strs.size()+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));
            for (int k = 1; k <= strs.size(); k++) {
                int zero = 0, one = 0;
                for (char c: strs[k-1]) {
                    zero += (c == '0');
                    one += (c == '1');
                }
                for (int i = 0; i <= m; i++) {
                    for (int j = 0; j <= n; j++) {
                        if (i >= zero && j >= one)
                            dp[k][i][j] = max(max(dp[k][i][j], dp[k-1][i-zero][j-one] + 1), dp[k-1][i][j]);
                        else
                            dp[k][i][j] = dp[k-1][i][j];
                    }
                }
            }
            return dp[strs.size()][m][n];
        }
    };
    

    However, the above code got MLE.
    and we can easily improve it to:

    class Solution {
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
            vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
            for (string s: strs) {
                int zero = 0, one = 0;
                for (char c: s) {
                    zero += (c == '0');
                    one += (c == '1');
                }
                for (int i = m; i >= zero; i--) {
                    for (int j = n; j >= one; j--) {
                        dp[i][j] = max(dp[i][j], dp[i-zero][j-one]+1);
                    }
                }
            }
            return dp[m][n];
        }
    };
    

    In order to avoid overlap the previous result, we should iterate from m/n to bottom.
    This solution got AC and run time is 256ms.

    Another way to think, if we got '111111111111111111....' at the begining, if we do not have enough 1s, we calculate much a lot unnecessary.
    If we sort the strs in certain order, when our 0s or 1s is not enough, we just can end out process.
    Then how to sort? Maybe the less 0s/1s, the better. I just count the 0s/1s and sort twice.
    I do not know whether 0 or 1 first come insufficient, so calculate twice.
    AC code is as follows and the run time is 13ms.

    class Solution {
        bool comp(string &a, string &b, char c) {
            int ca = count(a.begin(), a.end(), c), cb = count(b.begin(), b.end(), c);
            if (ca < cb)    return true;
            if (ca == cb)   return a.size() < b.size();
            return false;
        }
        int helper(vector<string>& strs, int m, int n) {
            int cnt = 0;
            for (int i = 0; i < strs.size(); i++) {
                int z = count(strs[i].begin(), strs[i].end(), '0'), o = strs[i].size() - z;
                m -= z;
                n -= o;
                if (m < 0 && n < 0) break;
                if (m >= 0 && n >= 0)   cnt++;
                else { m += z; n += o; }
            }
            return cnt;
        }
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
            vector<string> zero(strs), one(strs);
            sort(zero.begin(), zero.end(), [this](string &a, string &b){return comp(a, b, '0');});
            sort(one.begin(),  one.end(),  [this](string &a, string &b){return comp(a, b, '1');});
    
            return max(helper(zero, m, n), helper(one, m, n));
        }
    };
    

    Any suggestions will be appreciated.


  • 0
    I

    unfortunately, greedy solution now fails with:

    ["0000111","0000111111","01111111","0001","000111111","0000001111111","00011111","000011111","00000011","0111111","0000000001111111","0011","001111","00000001111","0011","0000111111111","0001111111","011111111"]
    4
    6


Log in to reply
 

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