题目链接：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.

这道题的要求是检查括号是否匹配，其中字符串只包含’(‘、’)’、’{‘、’}’、’[’ 和 ‘]’。

这道题的思路比较简单，用栈维护左括号，即在读取字符串的时候，遇到左括号就入栈。而在遇到右括号的时候，检测栈的状态，如果栈为空，说明没有与该右括号匹配的左括号，直接返回false；如果栈顶元素与该右括号不匹配，说明括号没有匹配，返回false；如果相匹配，这可以弹出栈顶元素，继续读取下一个字符了。

在判断括号是否匹配的时候，可以选择用if语句判断，也可以采用map实现。

时间复杂度：O(n)

空间复杂度：O(n)

======

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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