Solution: Open the Lock

Statement

You are given a lock with $4$ circular wheels, each containing digits '0' through '9'.

• The wheels can rotate freely and wrap around cyclically; turning '9' forward leads to '0', and turning '0’ backward leads to '9'.

• Each move consists of rotating one wheel by one position (either forward or backward).

The lock starts from the initial state "0000".

You are also given a list of deadends, where each string represents a lock position that is blocked; if the lock reaches any of these positions, it becomes stuck and can no longer be turned.

Your goal is to reach a given target combination by performing the minimum number of moves, starting from "0000" and avoiding all dead ends.

If it is impossible to reach the target, return -1.

Constraints:

• $1 \leq$ deadends.length $\leq 500$

• deadends[i].length $== 4$

• target.length $== 4$

• target will not be in the list deadends.

• target and deadends[i] consists of digits only.

Solution

The solution uses a Breadth-First Search (BFS) approach to find the minimum number of moves needed to reach the target lock combination from "0000", while avoiding dead ends. The key idea is to treat each $4-$digit combination as a node in an implicit graph, where an edge exists between two nodes if they differ by exactly one wheel turn (forward or backward) on a single digit. As each move has the same cost ($1$ turn), BFS is ideal for finding the shortest path (minimum moves) from the starting combination to the target. At each step, we generate all possible next combinations by turning each of the $4$ wheels forward and backward by one step. We skip any combinations that are dead ends or already visited to avoid cycles and unnecessary work. We process the search level by level: all combinations reachable in $k$ moves are processed before moving to $k + 1$ moves. As soon as we encounter the target combination, the current BFS level gives us the minimum number of turns required. If the queue becomes empty without reaching the target, we conclude that it is impossible to unlock the lock and return -1.

Now, let’s walk through the steps of the solution:

1. Create two character maps, nextSlot to map the current slot digit with its next slot digit$(0 → 1, 1→ 2,…, 9 → 0$), and prevSlot to map the current slot digit to its previous slot digit$(0 → 9, 9 → 8 …, 1 → 0)$.

2. Create a hash set, visited, initially containing all the combinations in deadends array.

3. Create a queue, pending to traverse all combinations in BFS.

4. Create an integer variable, turns, initially 0, to denote the number of wheel turns (BFS levels) made so far.

5. If visited contains the starting combination "0000" then we can never reach the target combination and will return -1 . ...