Remove Invalid Parentheses
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 ).
Example 1:
Input: "()())()" Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()" Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")(" Output: [""]
class Solution {
public:
int find1stInvalidindex(string s,string flag)
{
int open=0;
for(int i=0;i<s.size();++i)
{
if(s[i]==flag[0])
{
++open;
}else if(s[i]==flag[1])
{
--open;
}
if(open<0)
return i;
}
return -1;
}
void remove(string s,int pos,vector<string> &res,string flag)
{
int idx=find1stInvalidindex(s,flag);
if(idx==-1)
{
reverse(s.begin(),s.end());
if(flag[0]=='(')
remove(s,0,res,")(");
else
res.push_back(s);
return;
}
for(int i=pos;i<=idx;++i)
{
if(s[i]!=flag[1])continue;
if(pos!=i&&s[i-1]==flag[1])continue;
remove(s.substr(0,i)+s.substr(i+1),i,res,flag);
}
}
vector<string> removeInvalidParentheses(string s) {
vector<string> ans;
remove(s,0,ans,"()");
return ans;
}
};
