北大陈斌Python算法笔记（二）

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。


示例 1：

输入：s = "()"
输出：true
示例 2：

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

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


提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

class Solution:
    def isValid(self, s: str) -> bool:
        #用字典来存储括号对，键是左括号，值是右括号
        dic = {   '(':')',    '[':']',   '{': '}'  }
        #构造辅助栈
        stack = []
        #开始遍历每一个括号，只将左括号入栈，当下一次入栈的是 栈顶元素相对应 的右括号时，把栈顶元素出栈；如果不是，则直接返回False
        for i in s:
            #如果是左括号，则入栈
            if i in dic:
                stack.append(i)
            #如果是右括号且栈不为空，判断栈顶元素(stack[-1])是否与当前要入栈的元素（i）相匹配
            elif stack:
                #如果匹配，把栈顶元素出栈
                if dic[ stack[-1] ] == i:
                    stack.pop()
                #如果不匹配，则直接返回False
                else:
                    return False
            #如果右括号且栈为空，肯定不匹配，直接返回False
            else:
                return False

        #如果最后栈中元素为空，说明为有效括号，返回True
        if len(stack) == 0:
            return True
        #否则返回False
        else:
            return False

    def isValid(self, s: str) -> bool: