752. Open the Lock - Detailed Explanation

Problem Statement

You are given a lock with 4 circular wheels, each displaying digits from 0 to 9. The lock initially starts at "0000". You are also given a list of deadends—combinations that if reached, will cause the lock to become stuck—and a target combination you want to open the lock.

At each move, you can turn one wheel one digit forward or backward. Note that the wheels wrap around (i.e. turning '0' backward gives '9', and '9' forward gives '0'). Your goal is to determine the minimum number of moves required to transform the initial state "0000" into the target combination without ever entering any of the deadend combinations. If it is impossible to reach the target, return -1.

Example Inputs & Outputs

• Example 1:

  • Input:

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

  • Output: 6
  • Explanation:
    One possible solution is:

    "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"
    

    Total moves = 6.

• Example 2:

  • Input:

    deadends = ["8888"]
    target = "0009"
    

  • Output: 1
  • Explanation:
    The only move needed is turning the last digit from '0' to '9'.

• Example 3:

  • Input:

    deadends = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"]
    target = "8888"
    

  • Output: -1
  • Explanation:
    The target "8888" is unreachable because every adjacent combination leads to a deadend.

Constraints

• The length of each deadend string and the target is 4.
• The total number of possible combinations is 10,000 (from "0000" to "9999").
• The number of deadends is at most 500.

Hints

1. Breadth-First Search (BFS):
   Treat each valid combination as a node in a graph where an edge exists between two nodes if one can be reached from the other with a single move. Use BFS to find the shortest path from "0000" to the target.

2. Avoiding Deadends:
   Before starting the BFS, store all deadends in a set for quick lookup. Also, mark visited combinations to avoid cycles.

3. Neighbors Generation:
   For any given combination, generate its neighbors by incrementing or decrementing each digit (with wrap-around). For example, for digit '0', the neighbors are '1' (increment) and '9' (decrement).

4. Bidirectional BFS:
   For performance improvements, consider using bidirectional BFS (starting simultaneously from "0000" and the target) if the state space or deadends set is large.

Approaches

1. Standard BFS Approach

Idea:
Perform a breadth-first search starting from "0000". At each step, generate all valid neighboring combinations that are not deadends or visited. When the target is reached, return the number of moves taken.

Steps:

• Initialize a queue with the starting combination "0000" and a visited set containing "0000".
• For each combination, generate all neighbors by turning each digit up or down.
• If a neighbor equals the target, return the current move count + 1.
• If a neighbor is in the deadends set or has been visited before, skip it.
• Continue until the queue is empty, and if the target isn’t reached, return -1.

2. Bidirectional BFS Approach

Idea:
Instead of exploring from one end only, start BFS from both "0000" and the target simultaneously. This method reduces the search space and can be faster on large graphs.

Steps:

• Initialize two sets for the frontiers: one starting from "0000" and one from the target.
• Also maintain a visited set to avoid revisiting nodes.
• At each iteration, expand the smaller frontier by generating all valid neighbors.
• If there is any intersection between the two frontiers, the solution is found.
• Continue expanding until an intersection is found or all possibilities are exhausted.

Code Implementations

Python Code