一、题目描述

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.

题目解读：给定一个字符串，只包含‘（’，‘）’，‘{’，‘}’，‘[’，‘]’，这几个字符。判断这个字符是否是合法的。

思路：使用栈存储左括号，当遇到左括号入栈，当遇到右括号时，先检查栈顶元素，如果栈为空，或者栈顶元素不是左括号，说明该字符串非法。字符串中所有的字符遍历完后，如果栈空，说明字符串是合法的。

c++代码（0ms，14.97%）

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

其他代码：

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case '(': 
                case '{': 
                case '[': paren.push(c); break;
                case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
                case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
                case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};