leetcode 20 python 有效的括号

传送门

题目要求

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

有效字符串需满足：

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

示例 1:
输入: "()"
输出: true

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

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

思路一：

利用栈先进后出的规则，遍历给定字符串，若得到左括号（符合有效括号的出现顺序），将其压栈，若得到右括号，就从栈顶取出一个元素（前提是栈不是空的，若是空的，中断），如果取出的元素和右括号不是一对则中断，遍历一遍没问题，最后还要看栈中是否为空，若不为空，则说明左括号比右括号多，无效

→_→ talk is cheap, show me the code

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        bracket_dict = {"}":"{", "]":"[", ")":"("}
        # 底用None做一个哨兵，避免pop()操作时报错，简化判断过程
        stack = [None]
        for i in s:
            if i in bracket_dict:
                if bracket_dict[i] != stack.pop():
                    return False
            else:
                stack.append(i)
        # 注意加了哨兵后的判断条件为==1而不是==0
        return len(stack) == 1