Sharing my 208ms C++ solution


  • 0
    T
    class Solution {
        bool isValid(string s)
        {
            int n = s.length();
            if(n==0)
                return true;
            
            int i=0, count=0, j;
            while(i<n)
            {
                if(s[i]=='(')
                {
                    count++;
                    break;
                }
                else if(s[i]==')')
                    return false;
                else
                    i++;
            }
            
            for(j=i+1; j<n; j++)
            {
                if(s[j]=='(')
                    count++;
                else if(s[j]==')')
                    count--;
                    
                if(count<0)
                    return false;
            }
            
            return count==0;
        }
        
    public:
        vector<string> removeInvalidParentheses(string s) {
            vector<string> result;
            queue<string> myQueue;
            myQueue.push(s);
            
            bool isFound = false;
            while(myQueue.size()>0)
            {
                unordered_set<string> record;
                int n = myQueue.size();
                for(int i=0; i<n; i++)
                {
                    string str = myQueue.front();
                    myQueue.pop();
                    if(isValid(str))
                    {
                        isFound = true;
                        result.push_back(str);
                    }
                    else if(isFound==false)
                    {
                        int len = str.length();
                        for(int j=0; j<len; j++)
                        {
                            if(str[j]=='(' || str[j]==')')
                            {
                                string next = str.substr(0, j) + str.substr(j+1);
                                if(record.count(next)==0)
                                {
                                    myQueue.push(next);
                                    record.insert(next);
                                }
                            }
                        }
                    }
                }
                
                if(isFound)
                    return result;
            }
        }
    };

Log in to reply
 

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