The testcases are wrong?!


  • 1
    K

    I've come up with this DP solution:

    int findMaxForm(vector<string>& strs, int m, int n) {
    
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
        dp[0][0] = 0;
    
        for(int k = 0; k < strs.size(); k++) {
    
            int ones = 0, zeros = 0;
            for(int i = 0; i < (int)strs[k].length(); i++) {
                ones += (strs[k][i] == '1');
                zeros += (strs[k][i] == '0');
            }
    
            for(int i = n; i >= ones; i--) {
                for(int j = m; j >= zeros; j--) {
                    if(dp[i - ones][j - zeros] >= 0) {
                        dp[i][j] = max(dp[i][j], dp[i - ones][j - zeros] + 1);
                    }
                }
            }
    
        }
    
        return max(dp[n][m], 0);
    }
    

    But I got wrong answer in this test-case:

    ["10","0001","111001","1","0"]
    3
    4
    

    How the output is 3?

    In my understanding, output should be 2 ("111001","0").

    Then I modified my solution this way which is supposed to be wrong I guess and got accepted:

    int findMaxForm(vector<string>& strs, int m, int n) {
    
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
        for(int k = 0; k < strs.size(); k++) {
    
            int ones = 0, zeros = 0;
            for(int i = 0; i < (int)strs[k].length(); i++) {
                ones += (strs[k][i] == '1');
                zeros += (strs[k][i] == '0');
            }
    
            for(int i = n; i >= ones; i--) {
                for(int j = m; j >= zeros; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - ones][j - zeros] + 1);
                }
            }
    
        }
    
        return dp[n][m];
    }
    

    Now I am thinking test-cases for this problem are wrong. Can anyone please take a look?


  • 0
    K

    @StefanPochmann can you please explain it?


  • 0

    Form "10", "1" and "0"?


  • 0
    K

    @StefanPochmann "10", "1" and "0" consist of total 2 ones and 2 zeros. But in the testcase, m = 3, n = 4.

    Am I missing anything?


  • 0
    S

    Same question with you.

    ["10","0001","111001","1","0"]
    3
    4
    must return 2, instead of 3

    I think most answer posted, found the maximum number of strings can form with less than or equal to m 0s and less than or equal to n 1s.

    class Solution {
    public:
        const int INF = ~(1 << 31);
        unordered_map<int, int> cache;
        int solve(vector<string>& strs, int m, int n, int idx, vector<pair<int,int>> &cnt) {
            if(m == 0 && n == 0) return 0;
            if(m < 0 || n < 0) return -INF;
            if(idx >= strs.size()) return -INF;
            int key = idx * 1000000 + m * 1000 + n;
            if(cache.count(key)) return cache[key];
            return cache[key] = max(solve(strs, m, n, idx+1, cnt), solve(strs, m-cnt[idx].first, n-cnt[idx].second, idx+1, cnt)+1);
        }
        int findMaxForm(vector<string>& strs, int m, int n) {
            vector<pair<int,int>> cnt(strs.size(), {0, 0});
            for(int i = 0; i < strs.size(); ++i) {
                for(auto const &c: strs[i]) {
                    if(c == '0') ++cnt[i].first;
                    else if(c == '1') ++cnt[i].second;
                }
            }
            return max(0, solve(strs, m, n, 0, cnt));
        }
    };
    

  • 0
    K

    I understood now - the question asked to use maximum number of strings from m zeros and n ones, not necessarily using exactly m zeros and n ones. Thanks!


Log in to reply
 

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