首页 > 代码库 > Leetcode | Parentheses 相关

Leetcode | Parentheses 相关

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

只要左括号数大于1就可以添加左括号。只要右括号数大于左括号数就可以添加右括号。

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         vector<string> res;
 5         
 6         recursive(n, n, "", res);
 7         
 8         return res;
 9     }
10     
11     void recursive(int n1, int n2, string str, vector<string> &res) {
12         if (n1 == 0 && n2 == 0) {
13             res.push_back(str);
14             return;
15         }
16         
17         if (n1 >= 1) {
18             recursive(n1 - 1, n2, str + "(", res);
19         }
20         
21         if (n2 > n1) {
22             recursive(n1, n2 - 1, str + ")", res);
23         }
24     }
25 };

 网上查了一下,竟然还和Catalan数有关。

通项公式是: \(\frac{(2n)!}{(n+1)!n!}\) 

递推公式是 \(C_0=1\ and\ C_{n+1}=\sum\limits^n_{i=0}{C_{i}C_{n-i}}\)

n个+1和n个-1构成2n项\(a_1,a_2,\ldots,a_n\),其部分和满足\(a_1+a_2+\ldots+a_k\ge{}0,0\le{}k\le{}2n\)的序列个数等于第n个Catalan数\(C_n\)

Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

用了一个栈去实现。当前哪果是右括号,那么栈顶必须是对应的左括号才行。栈为空的话,也只能push左括号。

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if (s.empty()) return true;
 5         
 6         stack<char> st;
 7         
 8         for (int i = 0; i < s.length(); ++i) {
 9             if (st.empty()) {
10                 if (s[i] == ( || s[i] == [ || s[i] == {)  st.push(s[i]);
11                 else return false;
12             } else if (s[i] == ( || s[i] == [ || s[i] == {) {
13                 st.push(s[i]);
14             } else if (s[i] == )) {
15                 if (st.top() == () st.pop();
16                 else return false;
17             } else if (s[i] == ]) {
18                 if (st.top() == [) st.pop();
19                 else return false;
20             } else if (s[i] == }) {
21                 if (st.top() == {) st.pop();
22                 else return false;
23             } else {
24                 return false;
25             }
26         }
27         return st.empty();
28     }
29 };

重构一下:

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if (s.empty()) return true;
 5         
 6         stack<char> st;
 7         
 8         for (int i = 0; i < s.length(); ++i) {
 9             if (s[i] == ( || s[i] == [ || s[i] == {) {
10                 st.push(s[i]);
11                 continue;
12             } if (st.empty()) {
13                 return false;
14             } 
15             
16             if (s[i] == ) && st.top() != () return false;
17             if (s[i] == ] && st.top() != [) return false;
18             if (s[i] == } && st.top() != {) return false;
19             st.pop();
20         }
21         return st.empty();
22     }
23 };

 用map再重构,可以再简洁一些。

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if (s.empty()) return true;
 5         
 6         map<char, char> pars;
 7         pars[)] = (;
 8         pars[]] = [;
 9         pars[}] = {;
10         
11         stack<char> st;
12         
13         for (int i = 0; i < s.length(); ++i) {
14             if (pars.find(s[i]) == pars.end()) {
15                 st.push(s[i]);
16                 continue;
17             } if (st.empty()) {
18                 return false;
19             } 
20             
21             if (st.top() != pars[s[i]]) return false;
22             st.pop();
23         }
24         return st.empty();
25     }
26 };