存疑：判断终点为什么不能留在搜索部分

判断终点需要在一开始给出

  1. class Solution:
  2.     def openLock(self, deadends: List[str], target: str) -> int:
  3.         vis =set()
  4.         q =deque()
  5.         q.append('0000')
  6.         step=0
  7.         while len(q)>0:
  8.             for i in range(len(q)):
  9.                 s = q.popleft()
  10.                 if s in deadends:
  11.                     continue
  12.                 if s==target:
  13.                     return step
  14.                 for i in range(4):
  15.                     s1 =self.minuslock(s,i)
  16.                     if s1 not in  vis:
  17.                         vis.add(s1)
  18.                         q.append(s1)
  19.                     s2 = self.pluslock(s,i)
  20.                     if s2 not in  vis:
  21.                         vis.add(s2)
  22.                         q.append(s2)
  23.             step+=1
  24.         return -1

对字符串的操作,每一次搜索相邻的方式

不能直接对字符串中元素单独赋值
如果要赋值，必须要先转化成列表
列表转化成字符串直接不能用str 函数
如果列表要转成字符串，必须使用”.Join

  1.  def minuslock(self,s,num):
  2.         s= list(s)
  3.         if s[num]=='0':s[num]='9' 
  4.         else:s[num]=str(int(s[num])-1)
  5.         return ''.join(s)
  6.  def pluslock(self,s,num):
  7.         s= list(s)
  8.         if s[num]=='9':s[num]='0'
  9.     else: s[num]=str(int(s[num])+1)
  10.     return ''.join(s)

双边BFS搜索（trick)

不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。

  1. from collections import  deque
  2. class Solution:
  3.     def openLock(self, deadends, target: str) -> int:
  4.         vis = set()
  5.         q1= set()
  6.         q2 =set()
  7.         q1.add('0000')
  8.         q2.add(target)
  9.         step = 0
  10.         while len(q1) > 0 and len(q2)>0:
  11.             temp = set()
  12.             for s in q1:
  13.                 if s in deadends:
  14.                     continue
  15.                 if s in q2:
  16.                     return step
  17.                 vis.add(s)
  18.                 for i in range(4):
  19.                     s1 = self.minuslock(s, i)
  20.                     if  s1 not in vis:
  21.                         temp.add(s1)
  22.                     s2 = self.pluslock(s, i)
  23.                     if  s2 not in vis:
  24.                         temp.add(s2)
  25.             step += 1
  26.             q1=q2
  27.             q2 =temp
  28.         return -1
  30.     def minuslock(self, s, num):
  31.         s = list(s)
  32.         if s[num] == '0':
  33.             s[num] = '9'
  34.         else:
  35.             s[num] = str(int(s[num]) - 1)
  36.         return ''.join(s)
  38.     def pluslock(self, s, num):
  39.         s = list(s)
  40.         if s[num] == '9':
  41.             s[num] = '0'
  42.         else:
  43.             s[num] = str(int(s[num]) + 1)
  44.         return ''.join(s)