Bloomberg Valid Parentheses：最近未闭合括号的栈匹配

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版输入只含 ()[]{}，空串为有效；遇其他字符返回 false。
• 若面试明确允许普通文本混入，应决定忽略文字还是当作无效输入。

解题路线

1. 遇左括号压栈；遇右括号，栈必须非空且栈顶是对应左括号，否则立刻 false。
2. 扫描完必须栈空，防只出现左括号也被判有效。
3. 不变量是栈自底向上保存所有尚未闭合的括号，右括号只能闭合最后打开的一个；用 ({[]}) 与 ([)] 对照 dry run。

手动走一遍

‘([)]’：压 (、[，遇 ) 时栈顶 [ 与所需 ( 不符，立即 false；‘([])’ 全部匹配，最后栈空。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def valid_brackets(text):
    """Accept only three bracket types; every closer must match top opener."""
    matching = {")": "(", "]": "[", "}": "{"}
    opening = set(matching.values())
    stack = []
    for char in text:
        if char in opening:
            stack.append(char)
        elif char in matching:
            if not stack or stack.pop() != matching[char]:
                return False
        else:
            return False
    return not stack

复杂度

n 个字符 O(n) 时间，最坏 O(n) 栈空间；只一种括号时可用计数器，但三种嵌套不能只记深度。

易错点与追问

容易失分的边界

• 只比较左右括号数量。
• 闭合类型不匹配却继续。
• 末尾栈非空仍返回 true。
• 擅自加入其它字符处理规则。

继续深挖

• 如果有引号或转义括号？
• 流式输入如何跨 chunk 保存状态？
• 若要返回第一个错误位置？