20. 有效的括号 (Easy)
专题归类： 06-栈与堆 LeetCode 链接： https://leetcode.cn/problems/valid-parentheses/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
题目详细分析
- 数据范围： 1 ≤ s.length ≤ 10^4，字符集只有
()[]{}六种字符。 - 输入输出特征： 字符串只包含括号字符，不含空格、字母或数字。输出简单 boolean。
- 边界条件： 空字符串？题目说长度至少为 1，但即使为空也是有效的（没有不匹配的括号）。
- 核心约束： 括号必须 按顺序正确闭合。
([)]是无效的，因为[被)关闭了，但栈顶是(不匹配)。{[]}是有效的，因为内层的[]先闭合，然后外层的{}闭合。 - 隐藏条件：
- 奇数长度的字符串一定无效（括号必须成对出现）。
- 只检查数量不够，必须检查顺序。
)(虽然左右括号数相同但无效。 - 栈是最自然的解法——后遇到的左括号先被闭合（LIFO 特性）。
小白版直白理解
就像整理一摞盘子，每次看到左括号（开盘子的标记）就放在一摞上。每次看到右括号（收盘子的标记），就看最上面的盘子是不是对应的那个——是就拿走，不是就说明顺序错了。
比如 {[]}：
- 看到
{→ 放盘子（栈：{） - 看到
[→ 放盘子（栈：{ [） - 看到
]→ 最上面是[，匹配 → 拿走（栈：{） - 看到
}→ 最上面是{，匹配 → 拿走（栈：空） - 最后盘子空了 → 有效！
比如 ([)]：
- 看到
(→ 放（栈：(） - 看到
[→ 放（栈：( [） - 看到
)→ 最上面是[，不匹配)→ 无效！
解题思路
思路一：栈 + 哈希映射（推荐）
核心思想： 遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是否是对应的左括号。这利用了栈「后进先出」的特性：最后遇到的左括号需要最先被闭合。
def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in mapping: # 右括号
if not stack: # 栈已空但还有右括号 → 无效
return False
if stack[-1] != mapping[ch]: # 栈顶不匹配 → 无效
return False
stack.pop() # 匹配成功，弹出
else: # 左括号
stack.append(ch)
return not stack # 全部匹配完，栈应为空复杂度： 时间 O(n)，空间 O(n)
思路二：栈 + 直接匹配（不用哈希表）
用条件判断代替哈希映射，性能略高但可读性降低。
def isValid(s):
stack = []
for ch in s:
if ch in '({[':
stack.append(ch)
else:
if not stack:
return False
top = stack.pop()
if (ch == ')' and top != '(') or \
(ch == '}' and top != '{') or \
(ch == ']' and top != '['):
return False
return not stack思路三：替换法（不推荐，但提供另一种视角）
不断用空串替换成对的括号，如果最后字符串为空则有效。虽然直观但效率低。
def isValid(s):
while '()' in s or '{}' in s or '[]' in s:
s = s.replace('()', '')
s = s.replace('{}', '')
s = s.replace('[]', '')
return s == ''复杂度： 时间 O(n²)（每次 replace 都遍历），仅适合面试时提供思路对比。
易错点
- 空栈访问： 遇到右括号时，如果栈是空的（没有对应的左括号），直接返回 False。
not stack检查必不可少。 - 字符串遍历完后栈非空： 如果有未闭合的左括号，如
((()，遍历完后栈不为空，说明无效。返回时应该检查not stack。 - 不匹配顺序：
([)]类型——每个左括号都有对应的右括号，但顺序不对。栈特性天然防止这种情况。 - 奇数长度优化： 如果
len(s) % 2 == 1，直接返回 False，无需遍历。 - 多种括号类型： 必须区分不同类型的括号，
(]不匹配。哈希映射可以有效处理这种对应关系。
框架提炼
括号匹配模板（栈）：
def bracket_match(s, mapping):
"""通用括号匹配模板，mapping = {右括号: 左括号}"""
stack = []
for ch in s:
if ch in mapping: # 右括号
if not stack or stack[-1] != mapping[ch]:
return False
stack.pop()
else: # 左括号
stack.append(ch)
return not stack适用场景：
- 括号匹配校验（LeetCode 20）
- HTML/XML 标签闭合校验（将标签名映射为左右配对）
- 表达式求值中的括号解析