005 · Valid Parentheses

algorithm
Published

April 21, 2026

My First Thoughts

这道题一开始很容易理解成“括号数量是否配平”。

因为题目说左括号必须有对应的右括号，所以第一反应是：如果有一个 (，最后就必须有一个 )；如果有一个 [，最后就必须有一个 ]；如果有一个 {，最后就必须有一个 }。

那就可以分别维护三个计数器：

small  记录还没有闭合的 ()
middle 记录还没有闭合的 []
large  记录还没有闭合的 {}

从左到右遍历字符串：

  • 遇到左括号，对应计数加一
  • 遇到右括号，对应计数减一
  • 如果某个计数变成负数，说明右括号先出现了，直接返回 False
  • 最后如果三个计数都等于 0，说明数量刚好配平，返回 True

大概像这样：

def is_valid(s: str) -> bool:
    small = 0
    middle = 0
    large = 0

    for char in s:
        if char == "(":
            small += 1
        if char == "[":
            middle += 1
        if char == "{":
            large += 1

        if char == ")":
            small -= 1
        if char == "]":
            middle -= 1
        if char == "}":
            large -= 1

        if small < 0 or middle < 0 or large < 0:
            return False

    return small == 0 and middle == 0 and large == 0

这个想法并不是完全错的。它确实能检查出一些明显错误，比如：

s = "())"

遍历到最后一个 ) 时，small 会变成 -1，说明右括号多了。

它也能检查出这种情况：

s = "(()"

遍历结束后，small 还是 1，说明还有左括号没有闭合。

也就是说，计数器能判断“数量是否对得上”。但这道题不仅要求数量对，还要求闭合顺序对。

Why That Is Not Enough

计数器的问题是：它只知道每种括号还有几个没闭合，但不知道“最近打开的那个括号是谁”。

看这个例子：

s = "([)]"

按计数器逻辑走一遍：

(  small  +1
[  middle +1
)  small  -1
]  middle -1

最后 small = 0，middle = 0，large = 0。过程中也没有任何计数变成负数。

如果只看数量，这个字符串好像是合法的。但它其实不合法。

原因是：[ 还没有闭合的时候，先来了 )。也就是说，右括号试图跳过最近打开的 [，去关闭更早打开的 (。这违反了括号的嵌套顺序。

所以这题不是普通的计数问题，而更像“消消乐”：

遇到左括号：先存起来
遇到右括号：只能消掉最近存进去的那个左括号

如果最近存进去的是 [，那么下一个能消掉它的只能是 ]。不能用 ) 去消，也不能跳过它去消更早的 (。

因此实质上只需要维护一个有序的对象，每次左括号就append，存进去，出现右括号则比较最后一个，闭合则消掉，不闭合则返回FALSE

这就是 stack 的规则：后进先出。

Final Idea

用一个 stack 记录还没有被关闭的左括号。

从左到右遍历字符串：

  1. 如果是左括号，就放进 stack。
  2. 如果是右括号，就检查 stack 最后一个元素。
  3. 如果 stack 为空，说明右括号没有对应的左括号，返回 False。
  4. 如果 stack 最后一个左括号和当前右括号不匹配，返回 False。
  5. 如果匹配，就把 stack 最后一个元素弹出，表示这一对括号成功闭合。

遍历结束后，如果 stack 为空，说明所有左括号都被正确闭合，返回 True；否则返回 False。

这里的 stack 可以直接用 list 实现。它不是 set，也不是 dict，而是一个按“后进先出”规则使用的列表。

Why It Works

合法括号字符串的关键规则是：当前右括号必须关闭最近还没有关闭的左括号。

stack 正好保存了这些“还没有关闭的左括号”，并且最后一个元素就是最近打开的左括号。

所以每次遇到右括号时，只需要看 stack 顶部：

  • 如果类型匹配，就可以消掉这一对括号
  • 如果类型不匹配，说明闭合顺序错了
  • 如果 stack 为空，说明右括号来得太早了

最后 stack 为空，表示没有剩余未闭合的左括号。

Code

def is_valid(s: str) -> bool:
    # 可选优化：合法括号一定成对出现，长度为奇数时可以直接返回 False。
    # if len(s) % 2 == 1:
    #     return False

    pairs = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    stack = []

    for char in s:
        if char in "([{":
            stack.append(char)
        else:
            if not stack:
                return False

            if stack[-1] != pairs[char]:
                return False

            stack.pop()

    return len(stack) == 0

Complexity

Time \(O(n)\) — 每个字符最多入栈一次、出栈一次
Space \(O(n)\) — 最坏情况下所有字符都是左括号，都需要存在 stack 中

Takeaway

当题目要求检查“成对符号是否正确闭合”时，不要只看数量是否配平。真正重要的是闭合顺序：后打开的左括号必须先被关闭。遇到这种“最后进入的对象最先被处理”的问题，优先想到 stack。

← Quiz