C++ Clean and Short DP O(kmn) Time, O(mn) Space


  • 0
    F

    Where K is the size of the string array, and m n are number of zeros and ones.

    struct Solution {
        int findMaxForm(vector<string>& strs, int zeros, int ones) {
            vector<vector<int>> dp(zeros + 1, vector<int>(ones + 1));
            for (int i = 0; i < strs.size(); ++i)
            {
                int cur_z = 0, cur_o = 0;
                for (auto n : strs[i])
                    n == '0' ? cur_z ++ : cur_o ++;
                for (int z = zeros; z >= cur_z; -- z)
                    for(int o = ones; o >= cur_o; -- o)
                	    dp[z][o] = max(dp[z - cur_z][o - cur_o] + 1, dp[z][o]);
            }
            return dp[zeros][ones];
        }
    };
    

Log in to reply
 

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