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 ).

Examples:

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

分析：

首先强调一点，碰到括号的题目考虑堆栈，考虑堆栈，考虑堆栈！bfs的主要思路就是，每次找出一个invalid parentheses，然后把这个char去掉，把剩下的字符串重新push回queue。

解法bfs：

class Solution {
public:
    int findInvalidPos(string s) {
        stack<pair<char, int> > myStack;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                myStack.push(make_pair(s[i], i) );
            } else if (s[i] == ')') {
                if (myStack.empty() ) {
                    return i;
                }
                myStack.pop();
            }
        }
        int res = -1;
        if (!myStack.empty() ) {
            res = myStack.top().second;
        }
        return res;
    }

    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        if (s.size() == 0) {
            res.push_back("");
            return res;
        }
        deque<string> Q;
        unordered_set<string> visited;
        Q.push_back(s);
        while (!Q.empty() ) {
            string word = Q.front();
            Q.pop_front();
            if (visited.find(word) != visited.end() ) {
                continue;
            }
            visited.insert(word);
            int pos = findInvalidPos(word);
            if (pos == -1) {
                res.push_back(word);
                continue;
            }
            int start = 0;
            int end = word.size();
            if (word[pos] == '(') {
                start = pos;
            } else {
                end = pos + 1;
            }
            for (int i = start; i < end; i++) {
                if (word[i] != word[pos]) {
                    continue;
                }
                if (i != start && word[i - 1] == word[i]) {
                    continue;
                }
                // 注意这里有两种方法可以从字符串中删除一个char，其中insert函数要求插入的也是string
                string temp = word.substr(i, 1);
                word.erase(i, 1);
                Q.push_back(word);
                word.insert(i, temp);
                /*
                string temp = word.substr(0, i);
                if (i + 1 != word.size() ) {
                    temp.append(word.substr(i + 1, word.size() ) );
                }
                Q.push_back(temp);
                */
            }
        }
        return res;
    }
};