What does 'Valid Parentheses' mean in this problem?

A string is valid if every opening bracket has a matching closing bracket of the same type and all brackets are properly nested in order.

Why do I need a stack for this problem?

The stack enforces the correct nesting order by keeping track of unmatched opening brackets, which counts alone cannot guarantee.

Can I solve this problem using only counters for each bracket type?

No, using only counts fails when brackets are nested improperly, as a closing bracket may match the count but violate order, producing incorrect results.

What should I do if the string starts with a closing bracket?

Immediately return false because a closing bracket without a preceding matching opening bracket violates the stack-based order, signaling an invalid string.

How can I optimize checking large bracket strings?

Return early on the first mismatch and use a hash map to match bracket types, reducing unnecessary iterations while maintaining O(n) complexity.

#20

Easy

auto_awesome栈·bracket

LeetCode 题解工作台

有效的括号

给定一个只包括 '(' ， ')' ， '{' ， '}' ， '[' ， ']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例 1：输入： s = "()" 输出： t…

栈字符串

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

提示：

1 <= s.length <= 10⁴
s 仅由括号 '()[]{}' 组成

lightbulb

解题思路

方法一：栈

遍历括号字符串 $s$ ，遇到左括号时，压入当前的左括号；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否匹配，若不匹配，直接返回 false。

也可以选择遇到左括号时，将右括号压入栈中；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否是相等。若不匹配，直接返回 false。

两者的区别仅限于括号转换时机，一个是在入栈时，一个是在出栈时。

遍历结束，若栈为空，说明括号字符串有效，返回 true；否则，返回 false。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为括号字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        d = {'()', '[]', '{}'}
        for c in s:
            if c in '({[':
                stk.append(c)
            elif not stk or stk.pop() + c not in d:
                return False
        return not stk

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Do you handle mismatched closing brackets without scanning the entire string?
question_mark
Can you explain why using counts alone does not guarantee validity in nested brackets?
question_mark
Will you implement a stack-based approach to maintain proper bracket order?

warning

常见陷阱

外企场景

error
Relying only on counts of brackets, which ignores nesting order and can produce false positives.
error
Not checking if the stack is empty before popping, causing runtime errors for strings starting with closing brackets.
error
Failing to return early on mismatch, unnecessarily iterating over the remainder and reducing efficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Longest Valid Parentheses: Compute the length of the longest well-formed parentheses substring.
arrow_right_alt
Remove Invalid Parentheses: Generate all valid strings by removing the minimum number of invalid brackets.
arrow_right_alt
Minimum Add to Make Parentheses Valid: Determine how many brackets must be added to balance a string.

help

常见问题

外企场景

继续练习

#1 两数之和