打开转盘锁

本题解采用了双向广度优先搜索（BFS）算法。首先将起始点'0000'和目标点target分别加入到两个集合q1和q2中。算法交替从q1和q2中的一个较小的集合扩展，以此达到双向搜索的目的。每一步都检查当前节点是否出现在对方集合中，如果出现，表示找到了最短路径。如果没有，就将当前节点的所有相邻节点（通过拨动锁一位得到）添加到临时集合中，然后将q1和q2交换，继续下一轮搜索。搜索过程中会跳过出现在deadends集合中的节点。

时间复杂度: O(N)

空间复杂度: O(N)

from collections import deque

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        deads = set(deadends)  # 将deadends转换为集合以便快速查找
        q1, q2 = set(), set()  # 使用集合进行双向BFS
        q1.add('0000')  # 起始节点
        q2.add(target)  # 目标节点
        step = 0  # 初始步数为0

        while q1 and q2:  # 当两个队列非空时继续搜索
            if len(q1) > len(q2):  # 始终扩展较小的集合以提高效率
                q1, q2 = q2, q1
            temp = set()  # 临时集合存储新扩展的节点
            for cur in q1:
                if cur in deads:  # 如果当前节点是死亡节点，则跳过
                    continue
                if cur in q2:  # 如果当前节点已经在另一个集合中，说明找到了最短路径
                    return step
                deads.add(cur)  # 标记当前节点已访问
                for j in range(4):  # 遍历四个轮盘
                    up = self.plusOne(cur, j)  # 向上拨动一位
                    if up not in deads:
                        temp.add(up)
                    down = self.minusOne(cur, j)  # 向下拨动一位
                    if down not in deads:
                        temp.add(down)
            step += 1  # 增加步数
            q1, q2 = q2, temp  # 交换搜索方向
        return -1  # 如果两个队列都为空，则无法到达目标

    def plusOne(self, s: str, j: int) -> str:
        cha = list(s)
        if cha[j] == '9':
            cha[j] = '0'
        else:
            cha[j] = chr(ord(cha[j])+1)
        return ''.join(cha)
    def minusOne(self, s: str, j: int) -> str:
        cha = list(s)
        if cha[j] == '0':
            cha[j] = '9'
        else:
            cha[j] = chr(ord(cha[j])-1)
        return ''.join(cha)