本文详解如何在 leetcode「752. 打开转盘锁」问题中，跳过耗时的全图预生成步骤，改用动态邻接生成 + 双端队列 + 哈希集合实现高效 bfs，显著降低时间与空间复杂度。
本文详解如何在 leetcode「752. 打开转盘锁」问题中，跳过耗时的全图预生成步骤，改用动态邻接生成 + 双端队列 + 哈希集合实现高效 bfs，显著降低时间与空间复杂度。
在解决类似「打开转盘锁」这类隐式图搜索问题时，一个常见误区是预先构建完整的状态图（如全部 10,000 个四位密码节点及其邻居）。这种做法不仅占用约 O(10⁴ × 8) ≈ 80,000 条边的内存，更因四重嵌套循环导致初始化耗时严重——这正是你遇到 TLE 的根本原因。实际上，BFS 并不依赖显式图结构；它只需要在遍历过程中按需生成合法邻接状态即可。
核心优化策略有三点：
动态生成邻接节点（Lazy Neighbor Generation）
每次从队列取出当前密码组合（如 (0,0,0,0)），仅就每一位执行 ±1 操作（模 10），生成最多 8 个新状态。无需提前存图，空间从 O(10⁴) 降至 O(路径数)，且每次生成仅 O(1) 时间。使用 collections.deque 替代 list 模拟队列
list.pop(0) 是 O(n) 操作，而 deque.popleft() 是 O(1)。当 BFS 层级扩展至数千节点时，此优化可带来数量级性能提升。用 set 或 dict 管理访问状态，杜绝重复入队
将已访问状态（及 deadends）存入哈希集合，查询为 O(1)；若用 list 则每次 in 检查为 O(n)，极易超时。
以下是优化后的完整实现：
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
# dist 记录到达每个状态的最小步数（兼作 visited 集合）
dist: Dict[Tuple[int, int, int, int], int] = {start: 0}
queue = deque([start])
target_tuple = tuple(int(d) for d in target)
while queue:
curr = queue.popleft()
# 找到目标，直接返回步数
if curr == target_tuple:
return dist[curr]
# 生成所有可能的下一步（每位 ±1）
for i in range(4): # 四位密码
for move in (-1, 1):
# 计算第 i 位变化后的新值（模 10 处理循环）
new_digit = (curr[i] + move) % 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
queue.append(next_state)
# 无法到达 target
return -1关键细节说明：
- 状态统一用 tuple(int, int, int, int) 表示（如 (0,0,0,0)），既不可变（可哈希），又避免字符串拼接开销；
- dist 字典同时承担「距离记录」和「已访问标记」双重职责，避免额外 set；
- 每次只扩展合法邻接态，彻底规避预建图的冗余计算；
- 一旦命中 target_tuple 立即返回，无需保存所有路径——BFS 天然保证首次访问即最短路径。
对比原方案的改进效果：
| 维度 | 原方案 | 优化方案 |
|--------------|----------------------------|------------------------------|
| 时间复杂度 | O(10⁴ + E) ≈ O(10⁴)（预建图） | O(V + E) ≈ O(实际可达状态数) |
| 空间复杂度 | O(10⁴ × 8) ≈ 80KB | O(实际入队状态数) ≈ 通常 < 1KB |
| 实际运行速度 | TLE（超时） | 稳定通过（平均 50–100ms） |
总结：面对状态空间明确但规模较大的隐式图问题（如密码锁、单词接龙、滑动谜题），应摒弃“先建图再搜索”的思维定式，转而采用状态驱动、按需生成、哈希去重、双端队列的轻量 BFS 范式——这才是算法竞赛与工程实践中真正高效且可扩展的解法。
