本文讲解如何在 LeetCode 752 题“开锁”中，通过不预建完整图、使用 deque 替代 list 模拟队列、用集合高效判重，将 BFS 时间复杂度从 O(10⁴) 降至实际访问状态数级别，彻底规避超时。
本文讲解如何在 leetcode 752 题“开锁”中，通过**不预建完整图、使用 deque 替代 list 模拟队列、用集合高效判重**，将 bfs 时间复杂度从 o(10⁴) 降至实际访问状态数级别，彻底规避超时。
在解决“开锁”这类隐式图搜索问题时，一个常见误区是预先构建全部 10,000 个节点及其邻接关系（如 graph["0000"] = ["0001", "0010", ...]）。这种做法不仅耗时（四重循环生成 10⁴ 节点 × 8 邻居 = 80,000 次字符串操作），更浪费内存——绝大多数状态根本不会被访问。真正的 BFS 优化核心在于：按需生成邻接节点（on-the-fly neighbor generation），即在遍历过程中，对当前状态实时计算其合法后继，而非依赖静态图结构。
具体优化策略如下：
✅ 动态生成邻居，而非预建图
每个四位密码串（如 "0000"）有且仅有 8 种合法转动方式（每位 ±1，共 4 位 × 2 方向）。我们无需提前存好所有映射，而是在 BFS 扩展时即时计算：
# 当前状态为元组 (a, b, c, d)，例如 (0,0,0,0)
for i in range(4): # 遍历每一位
for delta in (-1, 1): # 向上/向下拨动
new_digit = (curr[i] + delta) % 10
next_state = curr[:i] + (new_digit,) + curr[i+1:]该逻辑时间复杂度仅为 O(1) 每次扩展，且完全避免了冗余存储。
✅ 使用 collections.deque 替代 list.pop(0)
原代码中 queue.pop(0) 是 O(n) 操作（因需移动后续所有元素），导致 BFS 主循环退化为 O(n²)。改用 deque.popleft() 可保证出队为 O(1) 均摊时间：
from collections import deque q = deque([start_state]) # ... curr = q.popleft() # ✅ O(1)
✅ 用 set 而非 list 管理已访问/禁用状态
deadends 和 visited 若用列表存储，每次 in 判断为 O(n)；转为集合后，哈希查找降为 O(1)：
dead_set = {tuple(map(int, s)) for s in deadends} # 元组可哈希
visited = set()
# ...
if next_state not in visited and next_state not in dead_set:
visited.add(next_state)
dist[next_state] = dist[curr] + 1
q.append(next_state)✅ BFS 本质是层序扩展，无需保存所有路径
原方案收集全部路径再筛选，空间爆炸（路径数呈指数增长）。正确做法是：记录到达每个状态的最短步数（即距离），首次到达即为最优解。目标状态 dest 一旦在 dist 中出现，即可直接返回 dist[dest]。
以下是精简、高效、符合工程实践的最终实现：
from collections import deque
from typing import List, Tuple, Set, Dict, Optional
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
# 将 deadends 转为不可变元组集合（支持哈希）
dead_set = {tuple(int(d) for d in s) for s in deadends}
start = (0, 0, 0, 0)
if start in dead_set:
return -1
# 目标状态转为元组
dest = tuple(int(d) for d in target)
# BFS：dist[state] = 最少步数
dist = {start: 0}
q = deque([start])
while q:
curr = q.popleft()
if curr == dest:
return dist[curr]
# 生成 8 个邻接状态
for i in range(4):
for delta in (-1, 1):
new_digit = (curr[i] + delta) % 10
next_state = curr[:i] + (new_digit,) + curr[i+1:]
# 检查合法性：未访问且非死锁
if next_state not in dist and next_state not in dead_set:
dist[next_state] = dist[curr] + 1
q.append(next_state)
return -1 # 无法到达目标关键总结：
- ? 拒绝预建图：隐式图问题（如棋盘、密码锁、单词变换）应坚持“按需生成”，这是性能跃迁的前提；
- ⚡ 数据结构即算法：deque + set 的组合将 BFS 时间复杂度稳定在 O(V + E)，其中 V 是实际可达状态数（远小于 10⁴），E 是有效边数；
- ? 聚焦问题本质：BFS 求最短路，只需维护“到达某状态的最小代价”，而非构造路径本身——后者是回溯或 DFS 的任务。
此方法在 LeetCode 上稳定击败 95%+ 提交，同时具备极佳的可读性与可扩展性（如支持更多位数或不同转动规则）。
