Simple DFS yet quite efficient in cpp


  • 3

    There must be some extra ( or ) that cannot be matched, so the first step is to count them - there are either extra ( or extra ) (there is no way that both of them are redundant).

    Then we can start to traverse and try different options (for example: if there are extra ( then we can either remove it or keep it when we encounter it, but if we keep it then it has to be matched by another ), so we are to use another value openCount to count the unmatched ( and when we reach the end of the string, all we need to do is check whether all the unmatched ( are matched, if they are then we can collect them)

    Note Using unordered_set to avoid duplicates.


    class Solution {
    public:
        void removeInvalid(string& s, int pos, string t, unordered_set<string>& v, int lCount, int rCount, int openCount){
            if(s[pos] == '\0') { if(!openCount) v.insert(t); return ; }
            if(s[pos] == '('){
                if(lCount) removeInvalid(s, pos+1, t, v, lCount-1, rCount, openCount);
                removeInvalid(s, pos+1, t+"(", v, lCount, rCount, openCount+1);
            }
            else if(s[pos] == ')'){
                if(rCount) removeInvalid(s, pos+1, t, v, lCount, rCount-1, openCount);
                if(openCount) removeInvalid(s, pos+1, t+")", v, lCount, rCount, openCount-1);
            }
            else removeInvalid(s, pos+1, t+s[pos], v, lCount, rCount, openCount);
        }
        vector<string> removeInvalidParentheses(string s) {
            int lCount = 0, rCount = 0;
            unordered_set<string> v;
            for(int i = 0; s[i]; ++i)
                if(s[i] == '(') lCount++;
                else if(s[i] == ')') lCount>0? lCount-- : rCount++;
            removeInvalid(s, 0, "", v, lCount, rCount, 0);
            return vector<string>(v.begin(), v.end());
        }
    };
    

  • 0
    S

    @LHearen Very clean solution, but some explanation might be helpful.


  • 1

    @Salkexy2 Critical explanation added, thank you!


Log in to reply
 

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