# 301. 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: [""]
# Solution
Approach 1: DFS.
Approach 2: BFS.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// DFS.
class Solution {
private:
unordered_set<string> res;
int minRemove;
string getRes(string& s, vector<int>& toRemove) {
int head = 0;
int tail = s.size() - 1;
string buf = "";
for (int i = 0; i <= toRemove.size(); ++i)
{
tail = (i == toRemove.size()) ? s.size()-1 : toRemove[i] - 1;
if (head <= tail)
buf += s.substr(head, tail-head+1);
head = tail + 2;
}
return buf;
}
void doRemoveInvalidParentheses(string& s, int idx, vector<int>& toRemove, int match) {
if (match < 0 || toRemove.size() > minRemove)
return;
while (idx < s.size() && s[idx] != '(' && s[idx] != ')')
idx++;
if (idx >= s.size())
{
if (match == 0 && toRemove.size() <= minRemove)
{
res.insert(getRes(s, toRemove));
minRemove = toRemove.size();
}
}
else
{
doRemoveInvalidParentheses(s, idx+1, toRemove, match + ((s[idx]=='(') ? 1 : -1));
toRemove.push_back(idx);
doRemoveInvalidParentheses(s, idx+1, toRemove, match);
toRemove.pop_back();
}
}
public:
vector<string> removeInvalidParentheses(string s) {
minRemove = s.size() + 1;
vector<int> tmp;
doRemoveInvalidParentheses(s, 0, tmp, 0);
return vector<string>(res.begin(), res.end());
}
};
Approach 2:
// BFS.
class Solution {
private:
bool isValid(string s) {
int match = 0;
for (int i = 0; i < s.size(); ++i)
{
if (match < 0)
return false;
if (s[i] == '(')
match++;
else if (s[i] == ')')
match--;
}
return match == 0;
}
public:
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> res;
queue<string> q;
if (isValid(s))
res.insert(s);
else
q.push(s);
while (!q.empty() && res.size() == 0)
{
unordered_set<string> tmpSet;
int qSize = q.size();
for (int i = 0; i < qSize; ++i)
{
string curr = q.front();
q.pop();
for (int j = 0; j < curr.size(); ++j)
{
string next = curr.substr(0, j) + curr.substr(j+1);
if (isValid(next))
res.insert(next);
else
tmpSet.insert(next);
}
}
for (unordered_set<string>::iterator it = tmpSet.begin();
it != tmpSet.end(); it++)
q.push(*it);
}
return vector<string>(res.begin(), res.end());
}
};