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.

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 .

6. Otherwise, insert the starting combination "0000", into pending and mark it as visited by inserting it into visited.

7. While there are elements in pending, iterate on all current level combinations, which is equivalent to the current queue size (number of states at this distance) times:

   1. Pop a combination from the queue and store it in currentCombination.

   2. If currentCombination == target, return turns.

   3. Otherwise, iterate on all four wheels and for each wheel index, $0..3$, generate the new combination:

      1. Turn the wheel forward using nextSlot to form a newCombination.

      2. If newCombination is not in visited, add it to the pending and mark it visited.

      3. Turn the same wheel backward using prevSlot to form another newCombination.

      4. If this is also unseen, add it to the pending and mark it visited.

   4. After iterating on all current level combinations, increment turns.

8. If we never reach the target combination, return -1.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for the solution we just discussed.

1. Building nextSlot and prevSlot maps, each mapping every digit to one neighbor. Each map has $n$ key–value pairs. So, the total time it takes: $O(n)$.

2. Inserting all $d$ deadend combinations of length $w$ into a hash set will cost: $O(d · w)$.

3. BFS over the state space:

   1. Total possible combinations of the lock:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\s$ ...