Leetcode: 301 删除无效的括号

301. 删除无效的括号

解题思路：

​ 这题采用了BFS的思路，因为题目要求中需要删除最少的无效括号来满足要求。所以我们采用了层级划分的方法。

• 每次递归都会遍历删除相同数量的括号所有字符串，判断其是否合法，合法则将其加入到结果res的向量中
• 每次递归都会在第一步后判断ans的数量是否大于0，大于则表示当前层级是删除最少的无效括号的情况，直接return即可
• 若无ans，则用nextSet记录下下一个层级的所有可能字符串(用str.substr(0,i)+str.substr(i+1)来进行切割)，△注意这里即便判断了s[i]==s[i-1]执行continue，还是需要set来进行去重操作，因为在最后只剩下一个括号时会导致重复情况。

以下是C++代码：

class Solution {
public:
    vector<string> ans;
    vector<string> removeInvalidParentheses(string s) {
        //采用BFS的方式遍历,用set+判断来去重
        unordered_set<string> set;
        set.insert(s);
        BFS(set);
        return ans;
    }

    void BFS(unordered_set<string> &curStr){
        //BFS层次遍历
        for(auto str:curStr){
            if(isValid(str)){
                ans.push_back(str);
            }
        }
        //在某个层级中有解则return
        if(ans.size()>0){
            return;
        }

        unordered_set<string> nextSet;
        for(auto s:curStr) {
            for (int i = 0; i < s.size(); i++) {
                if(i>0&&s[i]==s[i-1]) continue;
                if(s[i]=='('||s[i]==')') nextSet.insert(s.substr(0, i) + s.substr(i+1));
            }
        }
        BFS(nextSet);
    }

    bool isValid(string s){
        int count=0;
        int len=s.size();
        for(int i=0;i<len;i++){
            if(s[i]=='('){
                count++;
            }else if(s[i]==')'){
                count--;
            }
            if(count<0){
                return false;
            }
        }
        return count==0;
    }

};