Open the Lock
The key idea
Treat each 4-digit code as a node and each single wheel turn as an edge of weight 1. The fewest turns is then the shortest path in an unweighted graph, which BFS finds level by level. Deadends and already-seen codes are pruned so each of the 10000 states is expanded at most once.
Problem
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0' through '9'. The wheels rotate freely and wrap around: turning '9' up makes it '0', and turning '0' down makes it '9'. Each move turns one wheel by one slot.
The lock starts at "0000", a string representing the state of the 4 wheels. You are given a list of deadends; if the lock ever shows any of these codes, the wheels stop turning and you can never 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 reach target, or -1 if it is impossible.
Constraints
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target will not be in the list deadends
- target and deadends[i] consist of digits only
Examples
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Input: deadends = ["8888"], target = "0009"
Output: 1
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Complexity
Time: O(N^2 * A^N + D) Space: O(A^N + D)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM