C++刷leetcode(301. 删除无效的括号)【广度优先搜索】

糖逗

题目描述：

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:

输入: "()())()"
输出: ["()()()", "(())()"]
示例 2:

输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
示例 3:

输入: ")("
输出: [""]

#include <string>
#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>

using namespace std;


bool isvalid(string input){
        int count = 0;
        for(char c : input){
                if(c == '('){
                        count ++;         
                } 
                else if(c == ')'){
                        count--;
                        if(count < 0) return false;
                }        
        }

        return count == 0;
}

vector<string> bfs(string s){
        vector<string> res;
        unordered_set<string> store {{s}};
        queue<string> temp {{s}};
        bool flag = false;
        while(!temp.empty()){
                string temp1 = temp.front();
                temp.pop();
                if(isvalid(temp1)){
                        res.push_back(temp1);
                        flag = true;
                }
                if(flag) continue;
                for(int i = 0; i < temp1.size(); i++){
                        if(temp1[i] != '(' && temp1[i] != ')') continue;
                        string temp2 = temp1.substr(0, i) + temp1.substr(i+1);
                        if(store.count(temp2) == 0){
                                temp.push(temp2);
                                store.insert(temp2);
                        }
                }
        }
        return res;
} 


int main(void){
        string input;
        cin >> input;
        vector<string> res = bfs(input);
        for(int i = 0; i < res.size(); i++){
                cout << res[i] << endl;
                cout << "-----------" << endl;
        } 

        return 0;
} 

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... yong-setde-te-xing/
2.由于括号都是成对出现，且树的上一层和下一层字符串的个数为奇数和偶数，因此假设在第n层找到合法的字符串，那么n+1层所有字符串肯定不合法。因此，这一点特性成为本题能够使用广度优先搜索剪枝的关键。
3.

if(isvalid(temp1)){
                        res.push_back(temp1);
                        flag = true;
                }
                if(flag) continue;

注意这个代码，if(flag) continue；必须单独提出来写不能放在上面判断中。实际上，只要找到合法的字符串就停止下一步进行字符串剪裁了，不用再判断本次的字符串是否合法。字符串合法的判断只是确定是否放入res结果中，两个过程不是同步进行的。