Leetcode Link

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.

The lock initially starts at ‘0000’, a string representing the state of the 4 wheels. Example 1:

Input: deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202” Output: 6

Solution:

• BFS template
• Time Complexity: O(N^2∗A^N+D) where A is the number of digits in our alphabet, N is the number of digits in the lock, and D is the size of deadends.
• Space Complexity: O(A^N+D), for the queue and the set dead.

def openLock(self, deadends: List[str], target: str) -> int:
  def next_state(s):
    result = []
    for i in range(len(s)):
      ch = int(s[i])
      for d in (-1, 1):
        y = (ch + d) % 10
        yield s[:i] + str(y) + s[i+1:]

  que = collections.deque([("0000", 0)])
  deadends = set(deadends)
  visited = set()
  while que:
    state, num = que.popleft()
    if state == target:
      return num
    if state in deadends:
      continue
    for s in next_state(state):
      if s in visited:
        continue
      que.append((s, num + 1))
      visited.add(s)

  return -1