Open the Lock
01 · Problem
A lock has 4 circular wheels, each showing a digit from '0' to '9'. One move rotates a single wheel by one step forward or backward, and the wheels wrap around ('9' forward becomes '0', '0' backward becomes '9'). The lock starts at "0000".
You are given a list deadends. If the lock ever shows one of these combinations, the wheels jam and no further moves are possible, so a valid route must never pass through a deadend (including the start).
Given a 4-digit string target, return the minimum number of moves needed to reach it from "0000", or -1 if it is impossible. If target is "0000" and "0000" is not a deadend, return 0.
02 · Examples
deadends = ["0100","0010","1000","0001"], target = "0110"
4
The two-move routes 0000 -> 0100 -> 0110 and 0000 -> 0010 -> 0110 are blocked, as is every first move except turning a wheel backward. A shortest safe route is 0000 -> 9000 -> 9100 -> 9110 -> 0110.
deadends = ["0001"], target = "0009"
1
Turning the last wheel backward once takes 0 to 9, giving 0009 in a single move.
deadends = ["0000"], target = "1234"
-1
The starting combination itself is a deadend, so the lock is stuck immediately and no move can be made.
03 · Constraints
- 011 <= deadends.length <= 500
- 02deadends[i].length == 4 and target.length == 4
- 03deadends[i] and target consist of digits only
- 04target is not in deadends
04 · Optimal complexity
- Time
- O(10^4 * 8 + d)
- Space
- O(10^4 + d)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.