C++ BFS with unordered_map, 29ms


  • 1
    A

    If we use DP, there would be too many invalid searches.
    Instead, if we iterate through partially built results with an unordered_map, we don't have to waste time on invalid searches.

    60 / 60 test cases passed
    Status: Accepted
    Runtime: 29 ms

    class Solution {
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
            uint max = 0;
            unordered_map<short, uint> cand, pool, tmp; // Put {zeros, ones} into one short
            pool.reserve(m * n);
            tmp.reserve(m * n);
            for (auto& s : strs) { // Combine similar candidates since only the counts of 0/1 matter
                short zero = 0, one = 0;
                for (auto& c : s) {
                    if (c == '0') zero++;
                    else one++;
                }
                if (zero <= m && one <= n) cand[zero << 8 | one]++;
            }
            pool.emplace(m << 8 | n, 0);
            for (auto& c : cand) { // BFS, try to add each candidate into already built results
                short zero = c.first >> 8, one = c.first & 0xFF;
                tmp = pool;
                for (auto& p : pool) {
                    short zero_left = p.first >> 8, one_left = p.first & 0xFF;
                    for (uint i = 1, ii = c.second; i <= ii; i++) { // Each candidate represents several similar strings
                        if ((zero_left -= zero) >= 0 && (one_left -= one) >= 0) {
                            auto it = tmp.find(zero_left << 8 | one_left);
                            if (it == tmp.end()) tmp[zero_left << 8 | one_left] = p.second + i;
                            else if (p.second + i > it->second) it->second = p.second + i;
                        } else break;
                    }
                }
                pool.clear();
                pool.swap(tmp);
            }
            for (auto& p : pool) {
                if (p.second > max) max = p.second;
            }
            return max;
        }
    };
    

Log in to reply
 

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