Open the Lock
Medium · Stack & Strings · Array · Hash Table · String · Breadth-First Search
Problem
A lock has four wheels, each showing a digit from '0' to '9'. One move turns a single wheel one step up or down, and the digits wrap around: '9' turns up to '0', and '0' turns down to '9'. The lock starts at "0000".
deadends lists combinations that jam the lock: if the wheels ever show one of them, you are stuck. Return the fewest moves to reach target, or -1 if it cannot be reached. If "0000" itself is a dead end, the answer is -1.
Examples
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6
The direct routes through 0201 and 0102 are blocked, e.g. 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202.
Input: deadends = ["8888"], target = "0009" Output: 1
Turning the last wheel down once wraps 0 to 9.
Input: deadends = ["1000","9000","0100","0900","0010","0090","0001","0009"], target = "8888" Output: -1
Every first move lands on a dead end.
Constraints
- 1 <= len(deadends) <= 500
- len(deadends[i]) == 4
- len(target) == 4
- target is not in deadends
- target and deadends[i] contain digits only
Approaches
- Baseline: relax every move until nothing improves — time O(10^4 · 8 · L), space O(10^4)
Follow-up
Searching from both ends at once (from "0000" and from the target, always growing the smaller frontier) visits far fewer combinations on a large lock. The use cases below change the lock itself: any start and any number of wheels, and how many combinations are reachable within a budget of moves.
Related problems
Start free on Cariara · Coding problems · System design studio
