题目要求

给定一个只包含以下六种字符的字符串 s：

( ) { } [ ]

判断这个字符串是否有效。有效字符串必须同时满足三个条件：

  1. 每个左括号都由相同类型的右括号闭合。
  2. 左括号必须按照正确顺序闭合。
  3. 每个右括号都有一个对应的同类型左括号。

满足全部条件时返回 True，否则返回 False。

示例

输入输出
"()"True
"()[]{}"True
"(]"False
"([])"True
"([)]"False

约束

  • 1 <= s.length <= 10^4
  • s 只包含 ()[]{} 中的字符

LeetCode 提供的方法签名是：

class Solution:
    def isValid(self, s: str) -> bool:
        pass

Step 1：数量相同为什么仍然无效

先看两个字符串：

()[]{}
([)]

它们都有一个 ( 和一个 )、一个 [ 和一个 ]。如果只分别统计三种左括号和右括号的数量，这两个字符串都会通过检查。

当前 baseline 是：

分别统计每种左括号和右括号；数量全部相同就认为字符串有效。

这个 baseline 会在 ([)] 上给出错误答案。问题不在括号数量，而在闭合顺序：读到一个右括号时，它必须闭合最近遇到、但还没有被闭合的左括号。

把这个规则用于 ([)]：

位置当前字符还没有闭合的左括号判断
0((等待对应的 )
1[([[ 是最近还没有闭合的左括号
2)([) 不能闭合最近的 [，字符串无效

在位置 2 已经可以确定结果，不需要继续读取最后的 ]。虽然每种括号的总数最终都相同，但 ( 与 ) 跨过了尚未闭合的 [，形成了错误的交叉顺序。

用相同规则检查几个代表性输入：

输入结果第一个决定性理由
()[]{}有效每个右括号都闭合当时最近的同类型左括号
(]无效] 与最近还没有闭合的 ( 类型不同
([)]无效) 到来时，最近还没有闭合的是 [
([])有效] 先闭合 [，) 再闭合 (

现在这一版能做到：

  • 区分“括号数量相同”和“括号闭合顺序正确”。
  • 根据括号类型和最近未闭合位置，人工解释示例为什么有效或无效。

它还缺：

  • 一个能够对任意输入字符串执行上述判断的算法。
  • 一组可以直接运行的检查，用来证明实现与人工判断一致。

Step 2：先反复消除完整括号对

当前 baseline 已经能人工判断右括号是否按正确顺序闭合，但还没有一个可以执行的过程。

观察一个有效的嵌套字符串：

{[()]}

最内层的 () 已经是一个相邻的完整括号对，可以先消除：

{[()]}
  ↓ 消除 ()
{[]}
  ↓ 消除 []
{}
  ↓ 消除 {}
空字符串

无论嵌套多少层，一个非空的有效括号字符串都存在至少一对相邻的完整括号。消除这对括号后，剩余部分仍然保持原来的相对顺序，可以继续执行相同操作。

在上一版的人工判断后，增加一个可运行的 baseline：每一轮都删除三种相邻括号对；如果这一轮没有让字符串变短，就停止。最后只需判断是否已经消除为空字符串。

def is_valid_by_elimination(s: str) -> bool:
    while True:
        previous = s
        s = s.replace("()", "").replace("[]", "").replace("{}", "")

        if len(s) == len(previous):
            return s == ""


assert is_valid_by_elimination("()") is True
assert is_valid_by_elimination("()[]{}") is True
assert is_valid_by_elimination("(]") is False
assert is_valid_by_elimination("([])") is True
assert is_valid_by_elimination("([)]") is False
assert is_valid_by_elimination("{[()]}") is True
assert is_valid_by_elimination("(") is False
assert is_valid_by_elimination("]") is False

这个过程一定会停止：

  • 如果一轮发生消除，字符串长度至少减少 2。
  • 如果长度不变，说明已经没有任何相邻完整括号对，函数立即返回。

它也能正确区分无效顺序。例如 ([)] 不包含 ()、[] 或 {} 中的任何一个，因此第一轮长度不变，最终返回 False。

但这个 baseline 仍然会重复处理字符。对于深度为 n / 2 的嵌套字符串，每轮只能暴露下一层括号，可能需要 O(n) 轮；Python 的字符串替换还会扫描和复制当前字符串。因此最坏时间复杂度是 O(n²)，额外字符串空间是 O(n)。

现在这一版能做到：

  • 对任意满足题目字符约束的输入执行完整判断。
  • 用相邻完整括号对的消除顺序体现正确的嵌套关系。
  • 通过官方示例、深层嵌套和单侧缺失检查。

它还缺：

  • 避免反复扫描、复制已经检查过的字符。
  • 在一次从左到右的读取中完成匹配。

Step 3：只保留还没有闭合的左括号

当前 baseline 通过反复消除相邻括号对得到正确结果，但同一个字符可能在多轮替换中被反复扫描和复制。

重新看 Step 1 的判断规则：右括号到来时，只需要知道最近一个还没有闭合的左括号。更早的左括号必须等它闭合以后才能继续匹配。这正好是后进先出的顺序：最后遇到的未闭合左括号最先接受检查。

用一个栈 stack 保存已经读取、但还没有闭合的左括号：

  • 读到左括号时，把它压入栈。
  • 读到右括号时，它必须与栈顶左括号类型对应；匹配后弹出栈顶。
  • 如果右括号到来时栈为空，或者类型不同，立即返回 False。
  • 字符全部读取后，只有栈为空才返回 True。

对 ([)] 执行这一过程：

当前字符操作前的栈判断或操作操作后的栈
([]左括号入栈['(']
[['(']左括号入栈['(', '[']
)['(', '[']) 需要 (，但栈顶是 [，返回 False不再继续

再看有效嵌套 ([])：

当前字符操作前的栈判断或操作操作后的栈
([]左括号入栈['(']
[['(']左括号入栈['(', '[']
]['(', '[']与 [ 匹配，弹出['(']
)['(']与 ( 匹配，弹出[]

把上一版的重复替换替换为一次扫描：

import random


class Solution:
    def isValid(self, s: str) -> bool:
        closing_to_opening = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = []

        for char in s:
            if char in "([{":
                stack.append(char)
                continue

            if not stack or stack[-1] != closing_to_opening[char]:
                return False
            stack.pop()

        return not stack


solution = Solution()

# 官方示例。
assert solution.isValid("()") is True
assert solution.isValid("()[]{}") is True
assert solution.isValid("(]") is False
assert solution.isValid("([])") is True
assert solution.isValid("([)]") is False

# 深层嵌套、单侧缺失和剩余左括号。
assert solution.isValid("{[()]}") is True
assert solution.isValid("(") is False
assert solution.isValid("]") is False
assert solution.isValid("(()") is False

# 用固定种子生成 2,000 个短字符串，与 Step 2 的正确 baseline 对照。
rng = random.Random(20)
brackets = "()[]{}"

for _ in range(2_000):
    length = rng.randint(1, 12)
    candidate = "".join(rng.choice(brackets) for _ in range(length))
    expected = is_valid_by_elimination(candidate)
    actual = solution.isValid(candidate)
    assert actual is expected

为什么只检查栈顶就足够

扫描过程中，栈始终保存已经读取、但尚未闭合的左括号，并保持它们在原字符串中的先后顺序。

如果当前字符是右括号，正确顺序要求它先闭合最近的未闭合左括号，也就是栈顶：

  • 类型相同，弹出栈顶后，剩余栈仍然表示更外层的未闭合括号。
  • 类型不同，当前右括号跨过了栈顶左括号，已经无法通过后续字符修复。
  • 栈为空，说明当前右括号根本没有对应的左括号。

扫描结束时，非空栈表示仍有左括号没有被闭合。因此，return not stack 正好覆盖最后一种无效情况。

复杂度

每个字符只读取一次。每个左括号最多入栈一次、出栈一次，因此时间复杂度是 O(n)。最坏情况下全部字符都是左括号，栈会保存 n 个字符，额外空间复杂度是 O(n)。

现在这一版能做到：

  • 用一次从左到右的扫描判断括号类型与闭合顺序。
  • 在遇到空栈右括号或类型冲突时立即失败。
  • 正确识别读取结束后仍有未闭合左括号的情况。
  • 满足 O(n) 时间复杂度，并通过固定样例和随机差分测试。

算法部分已经完整。下一步只需要教程一致性检查和独立全文审核。