python hot 100——2 栈（自存）

20 有效的括号

1. 📖 题目要求

输入：一个只包含()[]{}的字符串，比如"()"、"()[]{}"、"(]"

输出：True或False

规则：左括号必须和相同类型的右括号闭合，且顺序正确。

2. 💡 整体思路

核心思想：遇到左括号就"记下来"，遇到右括号就看能不能和最近记下来的左括号配对。

为什么用栈？栈是"后进先出" —— 最后打开的括号，要最先关闭。就像俄罗斯套娃，最后放进去的那个，得先拿出来。

以"{[]}"为例，一步步走：

以"(]"为例：

3. 题解代码 & 扩展为完整程序的代码

class Solution: def isValid(self, s): """ :type s: str :rtype: bool """ dic = {'{': '}', '[': ']', '(': ')'} stack = [ ] for c in s: if c in dic: stack.append(c) else: # 当前是右括号 # 重点：先判断栈是不是空！空代表没有左括号和它配对 if len(stack) == 0: return False dic[stack.pop()] != c: return False return len(stack) == 1 if __name__ == "__main__": sol = Solution() test_cases = ["()", "()[]{}", "(]", "([)]", "{[]}", ""] for case in test_cases: print(sol.isValid(case))

4. 🛠 超详细代码逐行讲解

class Solution: def isValid(self, s): # 定义方法，self 固定写，s 是输入字符串 """ :type s: str # s 是字符串 :rtype: bool """ dic = {'{': '}', '[': ']', '(': ')'} # 字典：左括号→右括号映射 stack = [] # 初始化【栈】 for c in s: # 遍历字符串每个字符 if c in dic: # 如果 c 对应字典里的 key（左括号或'?'） stack.append(c) # 左括号入【栈】（记下来） else: # 当前是右括号 # 重点：先判断栈是不是空！空代表没有左括号和它配对 if len(stack) == 0: return False dic[stack.pop()] != c: # 否则 c 是右括号：弹出栈顶，查字典对比 return False # 不匹配，直接返回 False return len(stack) == 1 # 遍历完，检查栈是否只剩'?'

dic[stack.pop()] != c

等价拆开后的代码

top_char = stack.pop() # 第一步：弹出栈顶元素，同时栈里面删掉这个元素

match_right = dic[top_char] # 第二步：拿栈顶左括号，查它应该匹配什么右括号。

if match_right != c: # 第三步：拿 “应该的右括号” 和 “当前读到的右括号 c”对比

return False # 对不上，直接返回False，整个函数结束

• 如果两者不相等：括号配对失败 →return False直接结束程序。
• 如果两者相等：配对成功，什么都不做，继续循环。

注意：配对成功的时候，没有 return，直接往下走，继续处理下一个字符。

错误样例 s="( ]"

初始：stack = ['?']

• 第一轮 c='('，append，栈：['?','(']
• 第二轮 c=']']不在 dic 的 key，进入分支：

top_char = stack.pop() # top_char='('，栈变为 ['?']
match_right = dic[top_char] # match_right = ')'
if match_right != c: # ')' 和 ']' 不相等！条件成立
return False # 直接返回False，函数结束

5. 📚 本题用到的 Python 基础知识总结

6. 🚨 易错点提醒