Open the Lock

from collections import deque

class Solution(object):
  def zeroToNine(self,num, sign):
    
    if sign == '-':
      if num == 0:
        return '9'
      return str(num - 1)
    if num == 9:
      return '0'
    return str(num + 1)

  def getNeighbors(self,state):
    neighbors = []
    for i in range(4):
      x = state
      num = self.zeroToNine(int(x[i]), '+')
      x = x[:i] + num + x[i+1:]
      neighbors.append(x)
      x = state
      num = self.zeroToNine(int(x[i]), '-')
      x = x[:i] + num + x[i+1:]
      neighbors.append(x)
    return neighbors

      

  def openLock(self, deadends, target):
    if '0000' in deadends:
      return -1
    queue = deque(['0000'] )
    visited = set(['0000'])
    ans = 0
    while queue:
      size = len(queue)
      for _ in range(size):
        cur = queue.popleft()
        if cur == target:
          return ans
        neighbors = self.getNeighbors(cur)
        for neighbor in neighbors:
          if neighbor not in visited and neighbor not in deadends:
            queue.append(neighbor)
            visited.add(neighbor)
      ans += 1

    return -1
        
      


deadends = ["0201","0101","0102","1212","2002"]


target = "0202"
solution = Solution()
result = solution.openLock(deadends,  target)  
# y = solution.getNeighbors('0000')
# print(y)
print(result)