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 generateParenthesis(int n) { 4 vector res; 5 6 recursive(n, n, "", res); 7 8 return res; 9 }10 11 void recursive(int n1, int n2, string str, vector &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 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 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 } else 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 pars; 7 pars[')'] = '('; 8 pars[']'] = '['; 9 pars['}'] = '{ ';10 11 stack 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 }; Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
一开始就把思路定在，当碰到一个“（”右括号时，判断当前已经能够消掉的位置。后面也想过把值和位置作一个新的struct push到stack中，但是怎么就是想不到直接在stack中存位置呢。。。。
应该多思考一下和前面Valid Parentheses的关系。
总结思路就在于：
1. 栈顶为"("，当前字符为")"，这时就可出栈，同时记录当前消掉的长度；栈如果为空的话表明前面的符号全部被消掉了，所以长度就为i+1. 否则就是pop之后的新栈顶到当前位置的距离。也就是st.pop(); i - st.top();
2. 要检查栈顶，那么st不能为空。
1 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 if (s.empty()) return 0; 5 6 int max = 0; 7 stack st; 8 9 for (int i = 0; i < s.length(); ++i) {10 if (st.empty()) {11 st.push(i);12 } else {13 if (s[st.top()] == '(' && s[i] == ')') {14 st.pop();15 if (st.empty()) {16 if (i + 1 > max) max = i + 1;17 } else if (i - st.top() > max) {18 max = i - st.top();19 }20 } else {21 st.push(i);22 }23 }24 }25 26 return max; 27 }28 }; 第三次写，用栈。
1 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 if (s.empty()) return 0; 5 stack st; 6 7 int max = 0; 8 for (int i = 0; i < s.length(); i++) { 9 if (st.empty() || s[i] == '(') {10 st.push(i);11 } else if (s[st.top()] == '(') {12 st.pop();13 int len = st.empty() ? i + 1 : i - st.top();14 if (len > max) max = len;15 } else {16 st.push(i);17 } 18 }19 20 return max;21 }22 }; 这种求longest、maximum之类的题大多数也是可以用dp来做。
dp[i]表示到第i个位置的最长合法串。
1. 初始值都为0. 第一个符号无影响，所以可以从第二个位置开始。
2. 举例说一下dp[i]的更新，假设s="()(()())"。
i=7时，"()(()())"；
dp[i-1]=4就是到i-1=6为止的合法串长度，也就是"()(()())"；
此时需要检查j=i-dp[i-1]-1= 7-dp[6]-1=2的位置是否为"("，"()(()())"；
如果是，那么dp[i]=dp[i-1]+2，dp[7]=dp[6]+2=6;
此时还要把j之前的合法串合并起来。dp[i]+=dp[j-1], "()(()())",dp[7]+=dp[1]; dp[7]=8;
所以答案就是8.
1 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 if (s.empty()) return 0; 5 6 vector dp(s.length(), 0); 7 8 int max = 0; 9 for (int i = 1; i < s.length(); ++i) {10 int j = i - dp[i - 1] - 1;11 if (s[i] == ')' && s[j] == '(') {12 dp[i] = dp[i - 1] + 2;13 if (j > 0) {14 dp[i] += dp[j - 1];15 }16 if (dp[i] > max) max = dp[i];17 }18 }19 return max;20 }21 };