[C++] Clean Code - Rolling Queue


  • 0
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            vector<string> res;
            queue<string> q;
            q.push(s);
            set<string> visited;
            
            while (!q.empty() && res.empty()) {
                queue<string> next;
                while (!q.empty()) {
                    string s0 = q.front();
                    q.pop();
                    if (valid(s0)) {
                        res.push_back(s0);
                    }
    
                    int len = s0.size();
                    for (int i = 0; i < len; i++) {
                        if (s0[i] == '(' || s0[i] == ')') {
                            string s1 = s0;
                            s1.erase(i, 1);
                            if (!visited.count(s1)) {
                                visited.insert(s1);
                                next.push(s1);
                            }
                        }
                    }
                }
    
                swap(next, q);
            }
    
            return res;
        }
    
    private:
        bool valid(string s) {
            int open = 0;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == '(') {
                    open++;
                }
                else if (s[i] == ')' && --open < 0) {
                    return false;
                }
            }
            return open == 0;
        }
    };
    

Log in to reply
 

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