A (simple) c++ BFS solution


  • 0
    C
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) 
        {
            queue<string> q;
            vector<string> output;
            
            q.push(s);
            
            while(!q.empty())
            {
                unordered_set<string> foundStrings;
                bool found = false;
                int size = q.size();
                for(int i = 0; i < size; i++)
                {
                    string t = q.front();
                    if(isValidParen(t))
                    {
                        output.push_back(t);
                        found = true;
                    }
                    
                    q.pop();
                    if(!found)
                    {
                        for(int k = 0; k < t.size(); k++)
                        {
                            if(t[k] == ')' || t[k] == '(')
                            {
                                string toadd = t.substr(0, k) + t.substr(k + 1);
                                
                                if(foundStrings.find(toadd) == foundStrings.end())
                                {
                                    q.push(toadd);
                                    foundStrings.insert(toadd);
                                }
                                
                            }
                        }
                    }
                }
                
                if(found)
                    return output;
            }
            
        }
        
        bool isValidParen(string s)
        {
            if(s.size() == 0)
                return true;
                
            stack<char> stk;
            int index = 0;
            
            while(index < s.size())
            {
                char c = s[index];
                if(c == ')')
                    return false;
                if(c == '(')
                {
                    stk.push(c);
                    index++;
                    break;
                }
                
                index++;
            }
            
            while(index < s.size())
            {
                char c = s[index];
                
                if(c == '(')
                {
                    stk.push(c);
                }
                
                if(c == ')')
                {
                    if(stk.empty())
                        return false;
                    stk.pop();
                }
                index++;
            }
            
            
            return (stk.empty()) ? true : false;
        }
    };

  • 2
    M

    Func isValidParen() could be rewritten like that. Just have a counter to count still open parentheses, instead of using stack.

    bool isValidParen(const string &s) {
    
        int n = s.size();
        int open = 0;
    
        for(int i = 0; i < n; i++) {
            if (s[i] == '(') {
                ++open;
            } else if (s[i] == ')') {
                if (open > 0) {
                    --open;
                } else {
                    return false;
                }
            }
        }
        
        return !open;
    }
    

Log in to reply
 

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