share my C++ dp solution


  • 0
    N
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            unordered_map<string, int> f[2];
            f[0][""] = 0;
            int p = 0, q = 1;
            for (auto& c : s) {
                f[q].clear();
                vector<int> fmax(s.size(), INT_MIN);
                for (auto& p : f[p]) {
                    fmax[p.second] = max(fmax[p.second], (int)p.first.size());
                    int tmp = p.second + (c == '(' ? 1 : (c == ')' ? -1 : 0));
                    if (tmp == -1) continue;
                    fmax[tmp] = max(fmax[tmp], (int)p.first.size() + 1);
                }
                for (auto& p : f[p]) {
                    if (p.first.size() == fmax[p.second]) f[q][p.first] = p.second;
                    int tmp = p.second + (c == '(' ? 1 : (c == ')' ? -1 : 0));
                    if (tmp != -1 && fmax[tmp] == p.first.size() + 1) f[q][p.first + c] = tmp;
                }
                p ^= 1;
                q ^= 1;
            }
            vector<string> ret;
            for (auto& p : f[p])
                if (p.second == 0) ret.push_back(p.first);
            return ret;
        }
    };
    

Log in to reply
 

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