< Back




752. Open the Lock

Tricky question, requiring you to realize that you can easily setup the BFS relationship with a
little string manipulation. We're asked to determine the shortest path, least number of turns, for
a combination lock to reach the target combination. The lock has 4 wheels, with each location having
10 digits - 0 through 9. We're asked to turn one wheel at a time, and we can only rotate the wheel
1 number. The numbers can also work backwards, so 0 can be turned to 9, and 9 can be turned to 0.

With that, we know that for a given node, for example '0000', its neighbors are '1000', '9000',
'0100', '0900', '0010', '0090', '0001', and '0009'. To remember the neighbors we setup 2
dictionaries, prev_num and next_num, that we can index into to determine the options we have for
turning a wheel for a given number. We perform a BFS, and at each node we start from lock location
0 and iterate to 3, adding the neighbors of each lock location to the next step's queue - so long as
that location hasn't already been seen and isn't in the "deadends" set.

We continue to BFS until we hit the target, returning the number of steps it took to get there.

The solution is as follows:


  class Solution:
      def openLock(self, deadends: List[str], target: str) -> int:
          prev_num = {
              "0": "9",
              "1": "0",
              "2": "1",
              "3": "2",
              "4": "3",
              "5": "4",
              "6": "5",
              "7": "6",
              "8": "7",
              "9": "8"
          }

          next_num = {
              "0": "1",
              "1": "2",
              "2": "3",
              "3": "4",
              "4": "5",
              "5": "6",
              "6": "7",
              "7": "8",
              "8": "9",
              "9": "0"
          }

          seen = set(deadends)
          if "0000" in deadends:
              return -1
          seen.add("0000")
          queue = [("0000", 0)]

          while queue:
              curr_queue, queue = queue, []

              for node, steps in curr_queue:
                  if node == target:
                      return steps

                  for i in range(4):
                      next_node = list(node)
                      next_node[i] = prev_num[next_node[i]]
                      next_node = "".join(next_node)

                      if next_node not in seen:
                          seen.add(next_node)
                          queue.append((next_node, steps + 1))

                      next_node = list(node)
                      next_node[i] = next_num[next_node[i]]
                      next_node = "".join(next_node)

                      if next_node not in seen:
                          seen.add(next_node)
                          queue.append((next_node, steps + 1))

          return -1


_ Time Complexity:

  O(4(d + 10^4)) - Where d is the number of deadends.

_ Space Complexity:

  O(4(d + 10^4)) - Where d is the number of deadends.