有效的括号

🟢 Easy · 🏷️ 栈、字符串 · LeetCode#20

📖 题目

字符串只包含 ()[]{}，判断是否有效——左括号必须用同类型的右括号按正确顺序闭合。

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

🆕 新知识

Python 没有专门的栈类型，直接用 list 当栈：

stack = []
stack.append(x)   # 入栈
stack.pop()        # 出栈，返回被弹出的元素
stack[-1]           # 查看栈顶，不弹出
not stack           # 判断是否为空（[] 是假值）

💡 思路

括号匹配是后进先出的：最后出现的左括号，要最先被匹配到——这正是栈的特性。遇到左括号就入栈；遇到右括号，检查它和栈顶的左括号是不是一对，是就出栈，不是（或者栈已经空了）就说明无效。走完整个字符串后，栈必须刚好清空，否则说明还有左括号没被匹配。

用字典存配对关系，判断更简洁：pairs = {'(': ')', '[': ']', '{': '}'}。

💻 代码

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {'(': ')', '[': ']', '{': '}'}
        for c in s:
            if c in pairs:                          # 左括号，入栈
                stack.append(c)
            else:                                    # 右括号，检查匹配
                if not stack or pairs[stack[-1]] != c:
                    return False
                stack.pop()
        return not stack   # 栈空才说明全部匹配完

时间复杂度 O(n)，空间复杂度 O(n)，最坏情况全是左括号。