题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

• 1 <= s.length <= 10^4

• s 仅由括号 '()[]{}' 组成

  解题方法

  栈

  通过栈存储左括号，若与有括号相对应，则出栈，最后判断栈是否为空。
  可以在开始判断字符串中字符是否为偶数直接判断是否有效。
  时间复杂度O(n)，空间复杂度O(n+6)
  C++代码：

  class Solution {
  public:
    bool isValid(string s) {
        if((s.size()%2) != 0)   return false;
  
        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> tmp;
  
        for(char ch : s) {
            if(pairs.count(ch)) {
                if(tmp.empty() || tmp.top() != pairs[ch]) return false;
                tmp.pop();
            }
            else    tmp.push(ch);
        }
  
        return tmp.empty();
    }
  };