LinkedIn 括号匹配：从小括号扩展到多种括号

题意与假设

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

• 训练版接受 `()[]{}` 三类字符；其他字符抛 ValueError，空串为合法。题目只给从 `()` 扩展的方向，三类集合与错误行为为本文示例。

解题路线

1. 单类括号可用余额计数，但多个类型必须记录后进先出顺序：每见开括号就把它对应的闭括号压栈。
2. 每见闭括号，必须与栈顶期待字符相同；不相同或栈空立即失败。扫完后栈必须为空。
3. 若需要忽略普通文本，先单独定义 tokenization，再让扫描器跳过非括号字符；不要在无题面时默认忽略。

手动走一遍

`{[()]}` 逐步压入 `}`、`]`、`)`，三个闭括号依逆序弹出后为空，合法；`([)]` 在看到 `)` 时栈顶是 `]`，立即失败。仅计各类数量会错判后一例。

Python 参考实现

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

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

"""Training contract: only bracket symbols are accepted, with proper nesting.
The visible source describes a () first step then additional bracket types, but
omits how to handle non-bracket characters and the exact alphabet.
"""


def valid_brackets(expression: str, pairs: dict[str, str] | None = None) -> bool:
    if pairs is None:
        pairs = {"(": ")", "[": "]", "{": "}"}
    closing = set(pairs.values())
    if len(closing) != len(pairs) or set(pairs) & closing:
        raise ValueError("pairs must define disjoint unique opening/closing symbols")
    stack: list[str] = []
    for char in expression:
        if char in pairs:
            stack.append(pairs[char])
        elif char in closing:
            if not stack or stack.pop() != char:
                return False
        else:
            raise ValueError(f"unsupported character: {char!r}")
    return not stack

复杂度

N 个输入字符，每字符最多一次入栈/出栈，时间 O(N)，最深嵌套时空间 O(N)；只有单类括号时可降到 O(1) 额外空间。

易错点与追问

容易失分的边界

• 只比较每类开闭括号数量，忽略嵌套。
• 遇到空栈的闭括号不立即失败。
• 扫描结束未检查剩余开括号。
• 未问普通字符、转义、引号或注释是否参与语法。

继续深挖

• 如果字符串混有代码中的引号与注释怎么办？
• 如何返回首个错误位置？
• 流式输入怎样保持状态？
• 单类括号能否 O(1) 空间？