301. Remove Invalid Parentheses（BFS）

1.题目描述

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())()"]
")(" -> [""]

2.代码

方法：BFS
思想：从父串中依次剔除一个字符作为其子串，建立一棵树。通过BFS去遍历、检查这个树中结点子串的合法性，如果合法，则可以作为正确的匹配结果加入返回结果。

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        queue<string> q;
        unordered_set<string> visited;
        vector<string> res;

        q.push(s);

        while(!q.empty()) {
            s = q.front();
            q.pop();
            if(isValid(s))
                res.push_back(s);
            //保证了出现合法符号时，完成这一“层”的遍历即结束while
            /*如果当前“N层”的结果仍为空
             *说明至少需要剔除N+1才能得到正确匹配的子串
             */
            if(!res.empty()) continue;
            for(int i = 0; i < s.size(); ++i) {
                if(s[i] != '(' && s[i] != ')') continue;
                string ss(s);
                ss.erase(i, 1);
                if(visited.count(ss) == 0) {
                    visited.insert(ss);
                    q.push(ss);
                }
            }
        } 
        return res;
    }

    bool isValid(string s) {
        int count = 0;
        for(char c : s) {
            if(c == '(') ++count;
            else if(c == ')') --count;
            //保证括号是先左后右出现
            //若对于某次匹配存在先右后左，count < 0，返回错误
            if(count < 0) return false;
        }
        return count == 0;
    }
};