LeetCode Q301: Remove Invalid Parentheses (hard)

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

	class Solution {
	public:
	void helper(string s, vector<string>& res, int p){
	for(int i=0; i<s.length(); i++){
	if(s[i]!=')'&&s[i]!='(')
	continue;
	if(s[i]==')'){
	s.erase(i, 1);
	i--;
	}
	else
	break;
	}
	for(int i=s.length()-1; i>=0; i--){
	if(s[i]!=')'&&s[i]!='(')
	continue;
	if(s[i]=='('){
	s.erase(i, 1);
	i++;
	}
	else
	break;
	}
	if(s.empty())
	return;
	if(!res.empty()&&s.length()<res[0].length())
	return;
	stack<char> myStack;
	if(s[0]=='('||s[0]==')')
	myStack.push(s[0]);
	for(int i=1; i<s.length(); i++){
	char c = s[i];
	if(c!='('&&c!=')')
	continue;
	if(myStack.empty()){
	myStack.push(c);
	continue;
	}
	if(myStack.top()=='('&&c==')'){
	myStack.pop();
	continue;
	}else{
	myStack.push(c);
	}
	}
	if(myStack.empty()){
	if(res.empty())
	res.push_back(s);
	else{
	if(res[0].length()<s.length())
	res.clear();
	if(res.empty()||res[0].length()==s.length()){
	int i=0;
	for(i=0; i<res.size(); i++){
	if(res[i]==s)
	break;
	}
	if(i==res.size())
	res.push_back(s);
	}
	}
	return;
	}
	for(int i=p; i<s.length(); i++){
	if(s[i]!='('&&s[i]!=')')
	continue;
	string news = s;
	news.erase(i, 1);
	helper(news, res, i);
	}
	}
	vector<string> removeInvalidParentheses(string s) {
	vector<string> res;
	res.push_back(string(""));
	helper(s, res, 0);
	return res;
	}
	};

view raw Q301.cpp hosted with ❤ by GitHub