难度：简单

知识点：栈、字符串

地址：https://leetcode-cn.com/problems/valid-parentheses/

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

思路

• 通过题目我们可以得到一个结论，将字符串从左到右依次遍历，第一次遇到右括号时，一定会和最后遇到的左括号成一对。
• 将凑成一对的括号消除掉，继续向下遍历，并重复这个操作，最后将全部消除掉。
• 在这个过程中一下情况都可以返回 false，没有则可以返回 true
  • 当遇到右括号时，还没有遇到左括号
  • 当遇到右括号时，最后遇到的左括号不能凑成一对
  • 当遇到的右括号都凑对消除后，仍然有左括号残留

BRACKETS = {
    ")": "(",
    "}": "{",
    "]": "[",
}

class Solution:
    def isValid(self, s):
        '''
        按照解题思路，准备一个队列 stack
        1、遇到右括号时，推入到 stack 中
        2、遇到右括号时
            如果 stack 为空，则返回 False
            如果 stack 队尾不能和左括号凑成对，则返回 False
            如果 stack 队尾能和左括号凑成对，则将队尾弹出
        3、最后判断 stack 是否清空，如果没有清空，则返回 False
        执行用时： 44 ms , 在所有 Python3 提交中击败了 55.70% 的用户
        内存消耗： 13.7 MB , 在所有 Python3 提交中击败了 5.22% 的用户

        '''
        stack = []
        for c in s:
            if c not in BRACKETS:
                # 遇到的是左括号，加入到队列中
                stack.append(c)
                continue
            
            br = BRACKETS[c]    # 获取左括号
            if not stack:
                # 如果 stack 为空，则返回 False
                return False
            if stack[-1] != br:
                # 如果 stack 队尾不能和左括号凑成对，则返回 False
                return False
            # 如果 stack 队尾能和左括号凑成对，则将队尾弹出
            stack.pop()
        # 最后判断 stack 是否清空，如果没有清空，则返回 False
        return stack == []

s = Solution()
assert s.isValid('()') == True
assert s.isValid('()[]{}') == True
assert s.isValid('(]') == False
assert s.isValid('([)]') == False
assert s.isValid('{[]}') == True