Generate 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。

思路：可用于卡特兰数一类题目。

void getParenthesis(vector
     
       &vec, string s, int left, int right) {    if(!right && !left) { vec.push_back(s); return; }    if(left > 0)          getParenthesis(vec, s+"(", left-1, right);    if(right > 0 && left < right)          getParenthesis(vec, s+")", left, right-1);}class Solution {public:    vector
      
        generateParenthesis(int n) {        vector
       
         vec;        getParenthesis(vec, string(), n, n);        return vec;    }};
       
      
     

 

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.

思路： 栈。对 S 的每个字符检查栈尾，若成对，则出栈，否则，入栈。

class Solution {public:    bool isValid(string s) {        bool ans = true;        char ch[6] = {'(', '{', '[', ']', '}', ')'};        int hash[256] = {0};        for(int i = 0; i < 6; ++i) hash[ch[i]] = i;        string s2;        for(size_t i = 0; i < s.size(); ++i) {            if(s2 != "" && hash[s2.back()] + hash[s[i]] == 5) s2.pop_back();            else s2.push_back(s[i]);        }        if(s2 != "") ans = false;        return ans;    }};