LeetCode【0020】有效的括号

1 中文题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。其中有效字符串需满足下面的条件：

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

示例：

输入：s = "()"
输出：True

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

输入：s = "(]"
输出：False

输入：s = "([])"
输出：True

提示：

• $1\le s.length\le 10^4$
• s 仅由括号 ‘()[]{}’ 组成

---

2 求解方法：基于栈特性

2.1 方法思路

方法核心
首先使用字典存储括号的对应关系，提高查找效率。然后使用栈来存储左括号，遇到右括号时与栈顶左括号匹配。

实现步骤

（1）初始化阶段：

• 创建括号匹配的字典
• 创建空栈存储左括号

（2）遍历字符串阶段：

• 遇到左括号：直接入栈
• 遇到右括号：检查栈顶元素是否匹配

（3）处理右括号时：

• 检查栈是否为空
• 检查栈顶元素是否匹配
• 匹配成功则弹出栈顶元素

（4）最终检查阶段：

• 检查栈是否为空
• 空栈说明所有括号都匹配成功

方法示例

# 示例1
输入：s = "{[()]}"步骤演示：
1. 遇到 '{':
stack: ['{']2. 遇到 '[':
stack: ['{', '[']3. 遇到 '(':
stack: ['{', '[', '(']4. 遇到 ')':
检查栈顶 '(' 是否匹配 ')'
匹配成功，弹出 '('
stack: ['{', '[']5. 遇到 ']':
检查栈顶 '[' 是否匹配 ']'
匹配成功，弹出 '['
stack: ['{']6. 遇到 '}':
检查栈顶 '{' 是否匹配 '}'
匹配成功，弹出 '{'
stack: []7. 最终检查：
栈为空，返回 True

# 示例2：
输入：s = "([)]"1. 遇到 '(':
stack: ['(']2. 遇到 '[':
stack: ['(', '[']3. 遇到 ')':
栈顶是 '[' 而不是 '('，不匹配
直接返回 False

2.2 Python代码

class Solution:def isValid(self, s: str) -> bool:# 建立括号对应关系的字典pairs = {")": "(","]": "[","}": "{"}# 创建栈用于存储左括号stack = []# 遍历字符串中的每个字符for char in s:# 如果是右括号if char in pairs:# 如果栈为空或者栈顶元素与当前右括号不匹配，返回Falseif not stack or stack[-1] != pairs[char]:return False# 匹配成功，弹出栈顶元素stack.pop()# 如果是左括号，入栈else:stack.append(char)# 最后检查栈是否为空# 如果栈为空，说明所有括号都匹配成功# 如果栈不为空，说明有未匹配的左括号return len(stack) == 0

2.3 复杂度分析

• 时间复杂度：O(n)，其中n为字符串长度
  • 遍历字符串：O(n)
  • 字典查找：O(1)
  • 栈操作（push/pop）：O(1)
• 空间复杂度：O(n)
  • 字典大小：O(1)，固定只存储3个键值对
  • 栈空间：O(n)，最坏情况下存储所有左括号

---

3 题目总结

题目难度：简单
数据结构：栈、字典