如何在广度优先搜索中动态生成图以优化Leetcode开锁问题性能？

原方案的问题 #

你之前的实现预先生成包含10000个锁组合的完整图，这一步会消耗大量初始化时间，导致提交超时。另外，存储所有可能路径的做法也会占用过多内存，进一步拖慢程序运行效率。

优化核心思路 #

不需要提前构建整个图，而是在BFS遍历过程中动态生成当前节点的邻接点。每个锁组合的邻接点可以通过对四位数字分别进行加1、减1（取模10）得到，这个计算过程非常快，完全可以实时完成。

同时，优化BFS的实现方式：

• 不再存储所有路径，而是直接记录每个节点对应的步数，找到目标时立即返回结果
• 使用集合存储死锁和已访问节点，实现O(1)时间复杂度的存在性判断，避免重复访问或进入死锁

优化后的代码 #

from collections import deque
from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        # 死锁集合，快速判断是否不能访问
        dead_set = set(deadends)
        # 起点如果是死锁，直接返回-1
        if "0000" in dead_set:
            return -1
        
        # BFS队列：每个元素是(当前锁组合, 步数)
        queue = deque()
        queue.append(("0000", 0))
        # 已访问集合，避免重复遍历
        visited = set("0000")
        
        while queue:
            current, steps = queue.popleft()
            
            # 找到目标，返回步数
            if current == target:
                return steps
            
            # 动态生成所有邻接点
            for i in range(4):
                # 对当前位数字加1
                digit = int(current[i])
                new_digit = (digit + 1) % 10
                next_comb = current[:i] + str(new_digit) + current[i+1:]
                if next_comb not in visited and next_comb not in dead_set:
                    visited.add(next_comb)
                    queue.append((next_comb, steps + 1))
                
                # 对当前位数字减1
                new_digit = (digit - 1) % 10
                next_comb = current[:i] + str(new_digit) + current[i+1:]
                if next_comb not in visited and next_comb not in dead_set:
                    visited.add(next_comb)
                    queue.append((next_comb, steps + 1))
        
        # 遍历完所有可能仍未找到目标，返回-1
        return -1

# 测试示例
solution = Solution()
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
print(solution.openLock(deadends, target))  # 输出应为6

代码说明 #

1. 动态生成邻接点：对于每个锁组合，遍历四位数字，分别计算加1和减1后的新组合（取模10处理循环，比如9加1变成0，0减1变成9）。
2. BFS队列管理：使用deque实现队列，保证弹出队首元素的时间复杂度是O(1)，比原代码用列表pop(0)的O(n)高效很多。
3. 死锁与访问判断：用集合存储死锁和已访问节点，每次生成新组合时先判断是否合法（不在死锁且未访问过），合法才加入队列。
4. 提前终止：一旦在BFS中遇到目标组合，立即返回当前步数，这是BFS找最短路径的特性——第一次遇到目标时的步数就是最短路径长度。

内容的提问来源于stack exchange，提问作者Benjamin67