C++刷leetcode(301. 删除无效的括号)【广度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:48 编辑题目描述：
删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
示例 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 != '(' && temp1 != ')') 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 << endl;
cout << "-----------" << endl;
}
return 0;
}
注意事项：
1.参考链接：https://leetcode-cn.com/problems/remove-invalid-parentheses/solution/zhe-dao-ti-qiao-yong-bfsbing-li-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结果中，两个过程不是同步进行的。
页:
[1]