括号问题

**20. 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.

class Solution {
public:
    bool isValid(string s) {
        if(s.size()<=1)
          return false;
        stack<char> temp;
        
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='('||s[i]=='['||s[i]=='{')
              temp.push(s[i]);
            else
            {
                if(temp.size()==0)
                  return false;
                char top = temp.top();
                temp.pop();
                if(s[i]==')')
                {   
                    if(top!='(')
                    return false;
                }
                else if(s[i]==']')
                {  
                    if(top!='[')
                    return false;
                }
                else if(s[i]=='}')
                {  
                    if(top!='{')
                    return false;
                }
            }
        }
        
        return temp.empty();
    }
};

**32. 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.
代码如下：

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.size()<=1)
          return 0;
        stack<int> temp;
        int last = -1;
        int maxLen = 0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(')
              temp.push(i);
            else
            {
                if(temp.empty())
                  last = i;
                else
                {
                    //int t = temp.top();
                    temp.pop();
                    if(temp.empty())
                      maxLen = max(maxLen,i-last);
                    else
                      maxLen = max(maxLen,i-temp.top());
                }
            }
        }
        return maxLen;
    }
};

**22. 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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

代码如下：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> rec;
        dfs(n,n,"",rec);
        return rec;
    }
    void dfs(int left,int right,string out,vector<string> &rec)
    {
        if(left>right)
          return;
        if(left==0&&right==0)
          rec.push_back(out);
        if(left>0)
          dfs(left-1,right,out + "(",rec);
        if(right>0)
          dfs(left,right-1,out + ")",rec);
    }
};