# 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());
    }
};