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

糖逗

题目描述：

1. 
   
2. 删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
   
3. 
   
4. 说明: 输入可能包含了除 ( 和 ) 以外的字符。
   
5. 
   
6. 示例 1:
   
7. 
   
8. 输入: "()())()"
   
9. 输出: ["()()()", "(())()"]
   
10. 示例 2:
    
11. 
    
12. 输入: "(a)())()"
    
13. 输出: ["(a)()()", "(a())()"]
    
14. 示例 3:
    
15. 
    
16. 输入: ")("
    
17. 输出: [""]

复制代码

1. #include <string>
   
2. #include <iostream>
   
3. #include <vector>
   
4. #include <unordered_set>
   
5. #include <queue>
   
6. 
   
7. using namespace std;
   
8. 
   
9. 
   
10. bool isvalid(string input){
    
11.         int count = 0;
    
12.         for(char c : input){
    
13.                 if(c == '('){
    
14.                         count ++;        
    
15.                 }
    
16.                 else if(c == ')'){
    
17.                         count--;
    
18.                         if(count < 0) return false;
    
19.                 }       
    
20.         }
    
21. 
    
22.         return count == 0;
    
23. }
    
24. 
    
25. vector<string> bfs(string s){
    
26.         vector<string> res;
    
27.         unordered_set<string> store {{s}};
    
28.         queue<string> temp {{s}};
    
29.         bool flag = false;
    
30.         while(!temp.empty()){
    
31.                 string temp1 = temp.front();
    
32.                 temp.pop();
    
33.                 if(isvalid(temp1)){
    
34.                         res.push_back(temp1);
    
35.                         flag = true;
    
36.                 }
    
37.                 if(flag) continue;
    
38.                 for(int i = 0; i < temp1.size(); i++){
    
39.                         if(temp1[i] != '(' && temp1[i] != ')') continue;
    
40.                         string temp2 = temp1.substr(0, i) + temp1.substr(i+1);
    
41.                         if(store.count(temp2) == 0){
    
42.                                 temp.push(temp2);
    
43.                                 store.insert(temp2);
    
44.                         }
    
45.                 }
    
46.         }
    
47.         return res;
    
48. }
    
49. 
    
50. 
    
51. int main(void){
    
52.         string input;
    
53.         cin >> input;
    
54.         vector<string> res = bfs(input);
    
55.         for(int i = 0; i < res.size(); i++){
    
56.                 cout << res[i] << endl;
    
57.                 cout << "-----------" << endl;
    
58.         }
    
59. 
    
60.         return 0;
    
61. }

复制代码

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

1. if(isvalid(temp1)){
   
2.                         res.push_back(temp1);
   
3.                         flag = true;
   
4.                 }
   
5.                 if(flag) continue;

复制代码

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