3ms C++ Solution, preprocessing but simple recursion


  • 0
    W

    This problem takes me quite a long time. But I finally made it work. My approach is based on observation that an invalid string is either due to extra ')' or extra '('. For example, "( ) ) ) ( )" contains extra ')', and "( ) ( ( ( ) " contains extra '('. So an invalid string is either a ')'-invalid substring, or a '('-invalid substring, or a mixture of two. If an invalid string contains both, then it can be divided into three parts [ ')'-invalid substring ] + [valid substring] + [ '('-invalid substring ]. In addition, [ ')'-invalid substring ] can never interleave with [ '('-invalid substring ], because extra '(' will always be offset by extra ')'. With this in mind, we can divide the original string into three parts, ')'-invalid substring, valid substring, and '('-invalid substring. In addition, we should keep the number of extra ')' and the number of extra '('. Now, we can just run DFS to delete these extra ')' and '('.

    Edits: some more explanations
    0_1479429366464_upload-ffa3c079-4271-4276-b162-db0efb7dca14

    Here, I provide my code:

    public:
        vector<string> removeInvalidParentheses(string s) {
    	vector<string> result;
    	if(s.empty()) return vector<string>(1, "");
    	while(!s.empty() && s[0] == ')') s.erase(0, 1); // deleting leading ')'
    	while(!s.empty() && s.back() == '(') s.pop_back(); // deleting trailing '('
    	int leftEnd = -1; // last character of left_invalid_str
            int rightStart = s.size(); // First character of right_invalid_str
            int leftNb = 0, rightNb = 0; // Record the number of extra ')' or '('
    	for(int i = 0; i < s.size(); i++) { // With rightStart, we do not need a stack.
    		if(isalpha(s[i])) continue;
    		if(s[i] == '(') {
    			if(rightStart == s.size()) rightStart = i;
    			rightNb++;
    		}
    		else if(rightNb) {
    			if(rightNb == 1) rightStart = s.size();
    			rightNb--;
    		}
    		else {
    			leftEnd = i;
    			leftNb++;
    		}
    	}
    	string goodStr = s.substr(leftEnd + 1, rightStart - leftEnd - 1);
    	string leftStr = s.substr(0, leftEnd + 1);
    	string rightStr = s.substr(rightStart);
    	unordered_set<string> arrLeft, arrRight;
    	string leftPath = "", rightPath = "";
    	dfs(arrLeft, leftNb, leftStr, 0, leftPath, false, 0);
    	dfs(arrRight, rightNb, rightStr, 0, rightPath, true, 0);
    	for(auto& l : arrLeft)
    		for(auto& r : arrRight)
    			result.push_back(l + goodStr + r);
    	return result;
    }
    
    private:
        void dfs(unordered_set<string>& result, int invNb, string& str, int pos, string& path, bool isRev, int p) {
    	if(invNb == 0) {
    		int temp = pos;
    		for(int temp = pos; temp < str.size(); temp++) {
    			if(str[temp] == '(') p++;
    			else if(str[temp] == ')') p--;
    			if(p < 0) return;
    		}
    		if(p == 0) result.insert(path + str.substr(pos));
    		return;
    	}
    	if(pos == str.size() || p<0) return;
    	char validCh = isRev ? ')' : '(';
    	if(str[pos] == validCh || isalpha(str[pos])) {
    		if(str[pos] == '(') p++;
    		else if(str[pos] == ')') p--;
    		path += str[pos];
    		dfs(result, invNb, str, pos + 1, path, isRev, p);
    		path.pop_back();
    	}
    	else {
    		dfs(result, invNb - 1, str, pos + 1, path, isRev, p); // abandon
    		if(isRev) ++p;
    		else --p;
    		path += str[pos];
    		dfs(result, invNb, str, pos + 1, path, isRev, p); // not abandon
    		path.pop_back();
    	}
    }
    ```			i. Preprocessing, deleting leading ')' on left side, and deleting trailing '(' on right side
    			ii. Dividing the preprocessed string, s, into three parts: leftStr + goodStr, rightStr
    				1) leftStr start from the left end of s, it only contains extra ')'
    				2) rightStr start from the right end of s, it only contains extra '('
    				3) goodStr is a substring of s that has neither extra ')' nor extra '('. 
    				4) We can use an explicit stack or implicit stack to record the end of leftStr, the beginning of rightStr, and number of extra ')' in leftStr, leftNb, and the number of extra '(' in rightStr, rightNb
    			iii. Now we run DFS with backtracking to delete extra ')' in leftStr, and delete extra '(' in rightStr
    				1) A tricky point is that we must use a variable to indicate whether a partial solution is valid or not. We use an integer p
    				2) Every time we append a '(' in the partial solution, p++
    				3) Every time we append a ')' in the partial solution, p--
    				4) When p < 0, we know that the partial solution is invalid, we stop the DFS.			i. Preprocessing, deleting leading ')' on left side, and deleting trailing '(' on right side
    			ii. Dividing the preprocessed string, s, into three substrings (in sequence): leftStr + goodStr + rightStr
    				1) leftStr: starting from the left end of s, it only contains extra ')'
    				2) rightStr starting from the right end of s, it only contains extra '('
    				3) goodStr is a substring of s that has neither extra ')' nor extra '('. 
    				4) This partition operation can be realized by using an explicit stack or implicit stack to record the end of leftStr, the beginning of rightStr, and number of extra ')' in leftStr, and the number of extra '(' in rightStr.
    			iii. Now we run DFS with backtracking to delete extra ')' in leftStr, and delete extra '(' in rightStr
    				1) A tricky point is that we must use a variable to indicate whether a partial solution is valid or not. So, we keep an integer p = 0. This is also an implicit stack technique.
    				2) Every time we append a '(' in the partial solution, p++
    				3) Every time we append a ')' in the partial solution, p--
    				4) When p < 0, we know that the partial solution is invalid, we stop the DFS.			i. Preprocessing, deleting leading ')' on left side, and deleting trailing '(' on right side
    			ii. Dividing the preprocessed string, s, into three substrings (in sequence): leftStr + goodStr + rightStr
    				1) leftStr: starting from the left end of s, it only contains extra ')'
    				2) rightStr starting from the right end of s, it only contains extra '('
    				3) goodStr is a substring of s that has neither extra ')' nor extra '('. 
    				4) This partition operation can be realized by using an explicit stack or implicit stack to record the end of leftStr, the beginning of rightStr, and number of extra ')' in leftStr, and the number of extra '(' in rightStr.
    			iii. Now we run DFS with backtracking to delete extra ')' in leftStr, and delete extra '(' in rightStr
    				1) A tricky point is that we must use a variable to indicate whether a partial solution is valid or not. So, we keep an integer p = 0. This is also an implicit stack technique.
    				2) Every time we append a '(' in the partial solution, p++
    				3) Every time we append a ')' in the partial solution, p--
    				4) When p < 0, we know that the partial solution is invalid, we stop the DFS.

Log in to reply
 

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