本文讲解如何在“开锁”类bfs问题中跳过全图预构建，改用按需生成邻接状态的方式，结合deque队列与哈希集合优化，将时间复杂度从o(10⁴×8)降至o(n)，彻底规避超时问题。
本文讲解如何在“开锁”类bfs问题中跳过全图预构建，改用按需生成邻接状态的方式，结合deque队列与哈希集合优化，将时间复杂度从o(10⁴×8)降至o(n)，彻底规避超时问题。
在解决类似 LeetCode 752. Open the Lock 这类状态空间搜索问题时，一个常见误区是预先构建完整的状态图（如全部10,000个四位密码节点及其8个邻接节点）。这种做法不仅占用约80MB内存（10⁴节点 × 8字符串邻居 × ~20字节/字符串），更因四重嵌套循环（i,j,k,l）导致初始化耗时严重——即便未进入BFS主逻辑，已触发TLE。
真正高效的解法是延迟展开（Lazy Expansion）：不预建图，而是在BFS遍历过程中，对当前状态实时计算其所有合法后继状态。每个四位密码串（如 "0000"）有且仅有8种有效转动方式（每位±1，共4位×2方向），我们只需在访问该节点时即时生成这8个新状态，并校验其合法性（非deadend、未访问过）。
以下是优化后的标准实现：
from collections import deque
from typing import List, Tuple, Set
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
# 将deadends转为元组集合，便于O(1)查找；同时避免字符串重复构造
dead_set = 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 = {start: 0}
queue = deque([start])
target_tuple = tuple(int(x) for x in target)
while queue:
curr = queue.popleft()
if curr == target_tuple:
return dist[curr]
# 对每一位进行+1/-1转动（模10处理环形）
for i in range(4):
for step in (-1, 1):
# 构造新状态：仅修改第i位
new_digit = (curr[i] + step) % 10
nxt = curr[:i] + (new_digit,) + curr[i+1:]
# 合法性检查：不在deadend中，且未访问过
if nxt not in dead_set and nxt not in dist:
dist[nxt] = dist[curr] + 1
queue.append(nxt)
return -1 # 无法到达target
关键优化点解析：
- ✅ 零预构建开销：省去generate_lock_graph()中耗时的10⁴次循环，BFS启动即走；
- ✅ O(1)队列操作：使用deque.popleft()替代list.pop(0)，避免每次O(n)移除首元素；
- ✅ O(1)状态查重：用字典dist同时记录距离与访问状态，比list in explored快两个数量级；
- ✅ 状态紧凑表示：用tuple(int, int, int, int)替代字符串，减少内存占用与哈希计算开销；
- ✅ 早停机制：一旦curr == target_tuple立即返回，无需遍历所有路径。
注意事项：
- 切勿在BFS中保存所有路径（如原代码中的possiblePaths二维列表），这会导致空间爆炸（最坏O(10⁴×10⁴)）；BFS天然保证首次到达即最短路径，只需记录步数；
- deadends需提前转为集合（或字典），否则每次in检查为O(n)，整体退化为O(N²)；
- 模运算(x + step) % 10自动处理0→9和9→0的环形逻辑，无需条件分支。
此方法将实际运行时间从秒级降至毫秒级，完美适配LeetCode在线判题系统的性能要求。核心思想可迁移至所有隐式图搜索问题（如单词接龙、滑动谜题等）：让图结构“活”在算法逻辑中，而非静态存在于内存里。
