力扣22.括号生成

力扣22. 括号生成 - 力扣（Leetcode）

1.第一种，暴力dfs枚举 + 判断

 i.用dfs枚举出所有序列，然后判断合法括号序列

 1 class Solution {
 2 public:
 3     bool isLegal(string s) { //判断序列是否合法
 4         stack<char> stk;
 5         for (auto ch : s) {
 6             if (ch == '(') {
 7                 stk.push(ch);
 8             } else {
 9                 if (stk.empty()) {
10                     return false;
11                 }
12 
13                 stk.pop();
14             }
15         }
16         return stk.empty() ? true : false;
17     }
18 
19     vector<string> generateParenthesis(int n) {
20         vector<string> str;
21 
22         function<void(int, string)> dfs = [&](int cur, string s) {
23             if (cur == n * 2) {  //注意 一对括号是由两个符号组成
24                 if (isLegal (s)) {
25                     str.push_back(s);
26                 }
27                 return;
28             }
29 
30 
31             dfs(cur + 1, s + "(");
32             dfs(cur + 1, s + ")");
33             
34             return;
35         };
36 
37         dfs (1, "(");
38 
39         return str;
40     }
41 };

 ii.发现可以优化，当 左括号数量 大于 括号对数量n 时可以不用继续dfs了（快了24ms）

 1 class Solution {
 2 public:
 3     bool isLegal(string s) {
 4         stack<char> stk;
 5         for (auto ch : s) {
 6             if (ch == '(') {
 7                 stk.push(ch);
 8             } else {
 9                 if (stk.empty()) {
10                     return false;
11                 }
12 
13                 stk.pop();
14             }
15         }
16         return stk.empty() ? true : false;
17     }
18 
19     vector<string> generateParenthesis(int n) {
20         vector<string> str;
21 
22         function<void(int, string, int)> dfs = [&](int cur, string s, int leftnum) {
23             if (leftnum > n) { //加了这个判断，剪枝
24                 return;
25             }
26 
27             if (cur == n * 2) {
28                 if (isLegal (s)) {
29                     str.push_back(s);
30                 }
31                 return;
32             }
33 
34 
35             dfs(cur + 1, s + "(", leftnum + 1);
36             dfs(cur + 1, s + ")", leftnum);
37             
38             return;
39         };
40 
41         dfs (1, "(", 1);
42 
43         return str;
44     }
45 };

2.第二种，直接dfs生成有效括号序列，不判断（0ms，比第一种快了83ms）

在1.ii基础上继续发现，只要保证在任何时刻

左括号数量<括号对数量时，可以继续添加左括号

右括号数量< 左括号数量时，可以继续添加右括号

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         vector<string> str;
 5 
 6         function<void(int, string, int, int)> dfs = [&](int cur, string s, int leftnum, int rightnum) {
 7             if (cur == n * 2) {
 8                 str.push_back(s);
 9                 return;
10             }
11 
12             if (leftnum < n)
13                dfs(cur + 1, s + "(", leftnum + 1, rightnum);
14             if (rightnum < leftnum) //在任何时刻右括号的数量都要<=左括号的数量
15                dfs(cur + 1, s + ")", leftnum,rightnum + 1);
16             
17             return;
18         };
19 
20         dfs (1, "(", 1, 0);
21 
22         return str;
23     }
24 };