My C++ DFS Solution - 16ms


  • 39
    E
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            unordered_set<string> result;
            int left_removed = 0;
            int right_removed = 0;
            for(auto c : s) {
                if(c == '(') {
                    ++left_removed;
                }
                if(c == ')') {
                    if(left_removed != 0) {
                        --left_removed;
                    }
                    else {
                        ++right_removed;
                    }
                }
            }
            helper(s, 0, left_removed, right_removed, 0, "", result);
            return vector<string>(result.begin(), result.end());
        }
    private:
        void helper(string s, int index, int left_removed, int right_removed, int pair, string path, unordered_set<string>& result) {
            if(index == s.size()) {
                if(left_removed == 0 && right_removed == 0 && pair == 0) {
                    result.insert(path);
                }
                return;
            }
            if(s[index] != '(' && s[index] != ')') {
                helper(s, index + 1, left_removed, right_removed, pair, path + s[index], result);
            }
            else {
                if(s[index] == '(') {
                    if(left_removed > 0) {
                        helper(s, index + 1, left_removed - 1, right_removed, pair, path, result);
                    }
                    helper(s, index + 1, left_removed, right_removed, pair + 1, path + s[index], result);
                }
                if(s[index] == ')') {
                    if(right_removed > 0) {
                        helper(s, index + 1, left_removed, right_removed - 1, pair, path, result);
                    }
                    if(pair > 0) {
                        helper(s, index + 1, left_removed, right_removed, pair - 1, path + s[index], result);
                    }
                }
            }
        }
    };

  • -4
    This post is deleted!

  • 6
    T

    Similar solution but some conditions are added to avoid duplicated strings. As a result, vector is used instead of unordered_set and a 4ms solution is obtained.

    Then condition is : when you have continuous ( or ), only search from the head one:

    if (start == 0 || s[start - 1] != c) {
      for (int i = 0; start + i < s.length() && s[start + i] == c && i + 1 <= left; ++i) {
        dfs(s, start + i + 1, left - i - 1, right, open, path);
      }
    }
    

    The compte code:

    class Solution {
    public:
      vector<string> removeInvalidParentheses(string s) {
        int left = 0, right = 0;
        for (char ch : s) {
          if (ch == '(') {
            ++left;
          } else if (ch == ')') {
            if (left > 0) {
              --left;
            } else {
              ++right;
            }
          }
        }
        res.clear();
        dfs(s, 0, left, right, 0, "");
        return res;
      }
      
    private:
      void dfs(const string& s, int start, int left, int right, 
               int open, string path) {
        if (start == s.length()) {
          if (left == 0 && right == 0 && open == 0) {
            res.push_back(path);
          }
          return;
        }
        if (left < 0 || right < 0 || open < 0) return;
        
        char c = s[start];
        if (c == '(') {
          if (start == 0 || s[start - 1] != c) {
            for (int i = 0; start + i < s.length() && s[start + i] == c && i + 1 <= left; ++i) {
              dfs(s, start + i + 1, left - i - 1, right, open, path);
            }
          }
          
          dfs(s, start + 1, left, right, open + 1, path + c);
        } else if (c == ')') {
          if (start == 0 || s[start - 1] != c) {
            for (int i = 0; start + i < s.length() && s[start + i] == c && i + 1 <= right; ++i) {
              dfs(s, start + i + 1, left, right - i - 1, open, path);
            }
          }      
          
          dfs(s, start + 1, left, right, open - 1, path + c);
        } else {
          dfs(s, start + 1, left, right, open, path + c);
        }
      }
    
      vector<string> res;
    };

  • 1

    use sort and unique to delete the duplicated string.
    also add some explanation.
    the int number pair here is not success match, but the matched '(' that need find a ')' to be really matched.

    class Solution {
    //pair: the num of "(" which is marked to be pair and need find a ')'
    void helper(string s, int index, int left, int right, int pair, string path, vector<string>&res)
    {
        if(index>=s.size()){
            if(0==left&&0==right&&0==pair) res.push_back(path);
            return;
        }   
        
        if('('!=s[index]&&')'!=s[index]){
            helper(s, index+1, left, right, pair, path+s[index], res);
        }
        else{
            if('('==s[index]){
                //s[index] is marked as extra '('
                if(left>0) helper(s,index+1, left-1, right, pair, path, res);
                //s[index] is marked as matched '(' and is added to the path
                helper(s, index+1,left, right, pair+1, path+s[index],res);
            }
            if(')'==s[index]){
                //s[index] is marked as extra ')' 
                if(right>0) helper(s, index+1, left, right-1, pair, path, res);
                //s[index] is marked as matched ')' so the pair decrease 1
                if(pair>0) helper(s, index+1, left, right, pair-1, path+s[index], res);
            }
        }
    }
    public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        //left: extra num of '(' ; right: extra num of ')'
        int left=0, right=0;
        for(char c:s){
            if(c=='(')  left++;
            else if(c==')') left>0?left--:right++;
        }
        helper(s, 0, left, right, 0, "", res);
        sort(res.begin(), res.end());
        auto end_unique=unique(res.begin(), res.end());
        res.erase(end_unique, res.end());
        return res;
    }
    

    };


  • 0
    C

    class Solution {
    public:
    vector<string> removeInvalidParentheses(string s) {
    vector<string> result;
    unordered_map<string, int> visited;
    remove(s, result, 0, 0, '(', ')', visited);
    return result;
    }
    void remove(string s, vector<string>& result, int i, int j, char left, char right, unordered_map<string, int>& visited) {
    int stack=0, m;
    for(m=i; m<s.size(); m++) {
    //cout<<s[m]<<endl;
    if(s[m]==left)
    stack++;
    if(s[m]==right)
    stack--;
    if(stack<0)
    break;
    }
    //cout<<stack<<endl;
    if(stack<0) {
    for(int n=j; n<=m; n++) {
    if(s[n]==right && (n==j||s[n-1]!=right)) {
    string cur=s.substr(0, n)+s.substr(n+1);
    //cout<<cur<<endl;
    remove(cur, result, i, j, left, right, visited);
    }
    }
    return;
    }
    reverse(s.begin(), s.end());
    //cout<<s<<endl;
    if(left=='(')
    remove(s, result, 0, 0, ')', '(', visited);
    else {
    visited[s]++;
    if(visited[s] == 1) {
    result.push_back(s);
    }
    }
    }

    };


  • 0
    X
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            if(s.length() == 0) return vector<string>{s};
    		
    		//use dfs
    		vector<string> result;
    		unordered_set<string> visited;
    		int maxLength = 0;
    		dfs(result, visited, s, maxLength, 0, 0);
    		return result;
        }
    	void dfs(vector<string>& result, unordered_set<string> &visited, string s, int &maxLength, int pos, int cnt){
    		if(s.length() < maxLength || visited.find(s) != visited.end()) return; //early termination on other recursively dfs
    		visited.insert(s);
    		
    		//we do dfs at any location 
    		string tmp = s;
    		for(; pos < s.length(); pos++){
    			//at any location we can delete the current char and check whether it is OK or not
    			if(s[pos] == '(' || s[pos] == ')'){
    			    char deleted = s[pos];
    			    tmp.erase(tmp.begin() + pos);
    			    dfs(result, visited, tmp, maxLength, pos, cnt);
    			    tmp.insert(tmp.begin() + pos, deleted);
    			}
    		
    			if(s[pos] == '(') cnt++;
    			else if(s[pos] == ')') cnt--;
    			
    			//if it already fails, then we just break from here, because not matter what we do
    			//subsequently, we are not gonna save it
    			if(cnt < 0) break; 
    		}
    		
    		//if string is valid, we append it to the result
    		if(!cnt){
    		    if(s.length() > maxLength){
    		        result.clear();
    		        maxLength = s.length();
    		    }
    		    result.push_back(s);
    		}
    	}
    };
    

Log in to reply
 

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