面试题37：字符串中的括号

字符串经常出现括号的问题，主要就是产生括号对、判断括号对是否有效、最长的括号对子串。

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 class Solution {
 2 public:
 3     void helper(vector<string>& res,string path,int left,int right,int n){
 4         if(right > left || left > n || right >n) return;
 5         if(left == n){
 6             while(right < n){
 7                 path.push_back(')');
 8                 right++;
 9             }
10             res.push_back(path);
11             return;
12         }
13         path.push_back('(');
14         helper(res,path,left+1,right,n);
15         path.pop_back();
16         path.push_back(')');
17         helper(res,path,left,right+1,n);
18     }
19     vector<string> generateParenthesis(int n) {
20         vector<string> res;
21         string path;
22         helper(res,path,0,0,n);
23         return res;
24     }
25 };

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.

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

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.

 1 class Solution{
 2 public:
 3     int longestValidParentheses(string s){
 4         stack<int> lefts; // index of left parentheses.
 5         int len = s.length();
 6         if(len < 2) return 0;
 7 
 8         int start = -1;
 9         int res = 0;
10         for (int i=0;i<len;i++){
11             if(s[i] == '('){
12                 lefts.push(i);
13             }else{
14                 if(lefts.empty()){
15                     start = i;
16                 }else{
17                     lefts.pop();
18                     if(lefts.empty()){
19                         res = max(res,i - start);
20                     }else{
21                         res = max(res,i- lefts.top());
22                     }
23                 }
24             }
25         }
26         return res;
27     }
28 };