打开转盘锁 -- BFS

打开转盘锁
这里提供两种实现，单向BFS和双向BFS。

class OpenLock:"""752. 打开转盘锁https://leetcode.cn/problems/open-the-lock/"""def solution(self, deadends: List[str], target: str) -> int:"""单向BFS:param deadends: :param target: :return: """visited = set()# 将deadends初始化到visited数组中for deadend in deadends:visited.add(deadend)queue = []step = 0queue.append('0000')visited.add('0000')while queue:sz = len(queue)for i in range(sz):cur = queue.pop(0)if cur == target:return stepif cur in visited:continuevisited.add(cur)for j in range(4):up = self.plusOne(cur, j)if up not in visited:queue.append(up)down = self.minusOne(cur, j)if down not in visited:queue.append(down)step += 1return -1def plusOne(self, cur, j):if cur[j] == '9':return cur[:j] + '0' + cur[j+1:]else:return cur[:j] + str(int(cur[j])+1) + cur[j+1:]def minusOne(self, cur, j):if cur[j] == '0':return cur[:j] + '9' + cur[j + 1:]else:return cur[:j] + str(int(cur[j]) - 1) + cur[j + 1:]def solution2(self, deadends: List[str], target: str) -> int:"""双向BFS优化:param deadends: :param target: :return: """deads = set()visited = set()# 将deadends初始化到visited数组中for deadend in deadends:deads.add(deadend)q1 = set()q2 = set()q1.add('0000')q2.add(target)step = 0while q1 and q2:# 额外优化if len(q1) > len(q2):tmp = q1q1 = q2q2 = tmptemp = set()for cur in q1:if cur in deads:continueif cur in q2:return stepvisited.add(cur)for j in range(4):up = self.plusOne(cur, j)if up not in visited:temp.add(up)down = self.minusOne(cur, j)if down not in visited:temp.add(down)step += 1# 这里temp相当于q1，交换q1和q2q1 = q2q2 = tempreturn -1