BM44　有效括号序列¶

简单通过率 30.37%python3核心代码模式样例通过牛客 AC字符串栈

牛客原题　源码

讲解章节：栈

一句话

左括号入栈，右括号必须和栈顶配对，走完栈空才算合法。

解题思路¶

这题考什么¶

括号匹配的本质是「最近未闭合的左括号最先被闭合」，正是栈的后进先出。

遇到左括号 ( [ {：压栈，等着它的右括号；
遇到右括号：栈顶必须是与之配对的左括号，否则立刻返回 False；栈为空也返回 False（右括号多了，比如 "())"）。

扫完之后栈必须为空，否则说明还有左括号没闭合（比如 "(["）。

三处返回 False 对应三种非法：类型不配（"(]"）、右括号过剩（")"）、左括号过剩（"("）。栈里存的是左括号字符本身，因为判定右括号时要知道它该配哪一种。

数据规模与复杂度¶

0 <= |s| <= 1e4，时限「其他语言 2 秒」。每个字符最多进栈一次、出栈一次，时间 O(n)、空间 O(n)（全是左括号时栈高等于 n），正好是题面「备注」要求的量级。另一类朴素想法是反复把相邻的 "()"、"[]"、"{}" 删掉直到串不再变短，每轮扫一遍、最坏要扫 n/2 轮，1e4 的串就是 5e7 次字符操作外加大量字符串重建，比一趟栈慢出两个量级。

坑在哪¶

漏掉最后的「栈空」检查是最常见的错法：只在遇到右括号时校验，"[" 会被判成合法—— 而这正是示例 1，扫完必须确认没有左括号剩下。
三种括号各记一个计数器是行不通的：")(" 与 "([)]" 的各类计数都对得上，但序列非法。栈保留的是嵌套顺序，计数器把顺序信息丢了。
判空与比对的短路顺序不能颠倒：先 not stack 再 stack.pop()，反过来写会在空栈上直接 IndexError（输入 ")" 时立刻触发）。
空串是合法括号序列（题面定义的第一条），此时循环不执行、栈为空，返回 True。

样例复核¶

"["：唯一的字符是左括号，压栈后循环结束，栈非空，返回 False，与示例 1 一致。 "[]"：'[' 压栈，']' 查表得应配 '['，弹栈相等，扫完栈空，返回 True，与示例 2 一致。

参考实现¶

solutions/nowcoder/BM44/sol.py
from typing import List, Optional


class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}   # 右括号 -> 应当配对的左括号
        # 栈里存左括号字符本身：判定右括号时既要知道有没有、也要知道是哪一种
        stack: List[str] = []
        # 一趟扫描，字符只有「左括号」「右括号」两类分支
        for ch in s:
            if ch in pairs:
                # 栈空说明右括号多余；栈顶不配对说明类型交叉，如 "(]"
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                # 不在 pairs 里即左括号，压栈等待与之配对的右括号
                stack.append(ch)
        # 收尾检查不可省：栈里若还有左括号，说明它们至今没被闭合
        return not stack

BM44 有效括号序列¶