Open the Lock

I had this on a Pinterest L4 onsite, and the conversation that mattered came AFTER the BFS: "why is this not Dijkstra?" The right answer (every move costs 1, so BFS dominates Dijkstra by a log factor) was the actual signal. The catalog covers BFS over grids and strings, but it skipped this state-space BFS where the state is a numeric tuple and the deadend list shrinks the graph.

Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0' through '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.

You are given a list of deadends (strings), meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Examples

Example 1:

• Input: deadends = ["0201", "0101", "0102", "1212", "2002"], target = "0202"
• Output: 6
• Explanation: A valid path: 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202. Six turns.

Example 2:

• Input: deadends = ["8888"], target = "0009"
• Output: 1
• Explanation: Turn the last wheel from '0' to '9'. One turn.

Example 3:

• Input: deadends = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], target = "8888"
• Output: -1
• Explanation: All neighbors of 8888 are deadends, so the target is unreachable.

Example 4:

• Input: deadends = [], target = "0000"
• Output: 0
• Explanation: The starting state is already the target.

Constraints

• 0 <= deadends.length <= 500.
• deadends[i].length == 4.
• target.length == 4.
• target is not in the list of deadends.
• target and deadends[i] consist of digits only.

Follow-up

The state space has 10^4 = 10000 codes, with each having 8 neighbors (each of 4 wheels turning either way). Two-way BFS (one frontier from 0000, one from target) cuts the search by roughly the square root of the state space; great for tight loops but unnecessary at this scale.