DFS_C++_82ms_46.54%


  • 0
    class Solution {
    vector<string> res;
    unordered_set<string> check;//avoid of the duplicate string in res.
    int max = 0;
    //control for condition: "Remove the minimum number of invalid parentheses"
    public:
    vector<string> removeInvalidParentheses(string s) {
        //pre-process, remove the ')' at the beginning and '(' at the end of the string
        while(s.size() > 0){
            if(s[s.size() - 1] == '('){s.pop_back();}
            else{break;}
        }
        while(s.size() > 0){
            if(s[0] == ')'){s = s.substr(1);}
            else{break;}
        }
        if(s.empty()) {res.push_back(""); return res;}
        
        int left = 0, right = 0, lcl_max = 0;
        dfs(s,0,0,0,"");
        if(res.empty()){res.push_back("");}
        return res;
    }
    
    void dfs(string s, int left, int right, int lcl_max, string path){
        if(s.size() == 0){
            if(path.size() != 0 && left == right){
                if(lcl_max > max){max = lcl_max;}
                if(lcl_max == max && check.find(path) == check.end()){
                    res.push_back(path);
                    check.insert(path);
                    return;
                }
            }
            return;
        }
        if(s[0] == '('){
            dfs(s.substr(1),left+1,right,lcl_max+1,path+'(');// keep the '('
            dfs(s.substr(1),left,right,lcl_max,path);//discard the '('
        }else if(s[0] == ')'){
            if(left > right){
                dfs(s.substr(1),left,right+1,lcl_max,path+')');//keep the ')'
            }
            dfs(s.substr(1),left,right,lcl_max,path);//discard the ')'
        }else{// other chars
            dfs(s.substr(1),left,right,lcl_max,path + s[0]);
        }
    }
    };

Log in to reply
 

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