题目

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

解题

思路：利用栈，然后遍历字符串，字符如果是：

• ')', '}', 或者']'
  检查栈目前大小，如果是空，直接判断出不是有效字符串。
  如果不为空，将字符串和栈顶的字符串对比，如果是对应的左字符串，将栈顶字符出栈。
• '(', '{', 或者'[
  将字符入栈

最后检查栈的大小，如果是空，则这个字符串是有效字符串。

时间复杂度O(n)，空间复杂度O(n)

class Solution:
    def isValid(self, s: str) -> bool:
        d = {')': '(',
             '}': '{',
             ']': '['}
        l = []  # 使用列表来模拟栈
        for c in s:
            if c in d:              
                if len(l) == 0:     # 字符是右括号，且栈为空，s不是有效字符串
                    return False
                if l[-1] == d[c]:   # 检查栈顶字符，如果栈顶字符是对应的左括号，出栈
                    l.pop()
                else:
                    return False
            else:
                l.append(c)
        return len(l) == 0