C++ DFS solution (9ms)


  • 0
    R
        int findMaxForm(vector<string>& strs, int m, int n) {
            if (m == 0 && n == 0) return 0;
            int s = strs.size(), i = 0;
            sort(strs.begin(), strs.end());
            vector<int> M(s, 0), N(s, 0);
            for (string str : strs)
            {
                for (char c : str)
                {
                    if (c == '0')
                    {
                        ++M[i];
                    }
                    else if (c == '1')
                    {
                        ++N[i];
                    }
                }
                ++i;
            }
            unordered_map<int, int> mem;
            return find(0, m, n, M, N, mem);
        }
        int find(int b, int m, int n, vector<int>& M, vector<int>& N, unordered_map<int, int>& mem)
        {
            int key = b << 14 | m  << 7 | n;
            if (mem.count(key)) return mem[key];
            if (m < 0 || n < 0) return -1;
            if (m == 0 && n == 0) return mem[key] = 0;
            int ret = 0, s = M.size(), x = b;
            for (; x < s; ++x)
            {
                if (ret > s - x) break;
                if (x > b && M[x] == M[x-1] && N[x] == N[x-1]) continue;
                ret = max(find(x+1, m - M[x], n - N[x], M, N, mem) + 1, ret);
            }
            return mem[key] = ret;
        }
    

Log in to reply
 

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