C++ 8ms DFS solution with comments


  • 5
    S
    void DFS(int ind, int l, int r, const string &s, vector<string> &ret, string &path) {
        // l is the number of '('s and r is the number of ')'s in path
    	if(r>l) return;
    	
    	if(ind==s.size()) {
    	    // if !ret.empty(), we find one longest valid string
    		if(l==r && (ret.empty() || path.size()==ret[0].size())) 
    		    ret.push_back(path);
    		return;
    	}
    	
    	if(!ret.empty())
    	    if(path.size() + s.size() - ind < ret[0].size()) return;
    	
    	char c = s[ind++];
    	path.push_back(c);
    	if(c!='(' && c!=')')
    		DFS(ind,l,r,s,ret,path);
    	else if(c=='(')
    		DFS(ind,l+1,r,s,ret,path);
    	else 
    		DFS(ind,l,r+1,s,ret,path);
    	
    	path.pop_back();
    	if(c!='(' && c!=')')
    	    DFS(ind,l,r,s,ret,path);
    	else {
    	    //once decide to give up current '(' or ')', we do not need to try the continuous '('s or ')'s
    	    while(c==s[ind]) ++ind;
    	    DFS(ind,l,r,s,ret,path);
    	}
    }
    
    vector<string> removeInvalidParentheses(string s) {
    	vector<string> ret;
    	string path;
    	DFS(0,0,0,s,ret,path);
    	if(ret.empty()) return {""};
    	return ret;
    }

  • 0
    C

    Could you explain what is the meaning of this part?

    path.pop_back();
    if(c!='(' && c!=')')
        DFS(ind,l,r,s,ret,path);
    else {
        //once decide to give up current '(' or ')', we do not need to try the continuous '('s or ')'s
        while(c==s[ind]) ++ind;
        DFS(ind,l,r,s,ret,path);
    }
    

  • 0
    S

    Before this part, we have the following:
    path.push_back(c);
    which means we want to try a string which contains current character. Of course, this character might be '(', ')' or something else.

    Then we must also try a string which does not contain current character. Thus, we have to:
    path.pop_back();
    And if the current character is neither '(' nor ')', we just pop it out from the path string;
    however, let's assume it's '('. In order to be more effective, we can simply skip the continuous '('s.


  • 0
    C

    Thank you for your comments. Now I can understand your code. Btw, I find that "DFS(ind,l,r,s,ret,path);" inside the if statement "if(c!='(' && c!=')')" can be removed.


  • 0
    A

    I agree with you too. Since if the character is neither '(' nor ')', it should be kept in the path string.


  • 0
    N

    What would be the time complexity for this solution ?


Log in to reply
 

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