492. Open the Lock
A combination lock has 4 wheels, each showing a digit 0–9. A wheel can rotate freely in either direction: turning 9 forward gives 0, and turning 0 backward gives 9. One move rotates exactly one wheel by one notch.
The lock starts at "0000". You are given a list of deadends — combinations that jam the lock permanently the instant the wheels show them — and a target combination.
Return the minimum number of moves needed to reach target without ever displaying a deadend, or -1 if it cannot be done. Note the start counts too: if "0000" itself is a deadend, the lock can never be turned at all.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: One shortest sequence is 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202: six single-notch turns, never landing on a deadend. A more direct-looking route like 0000 → 0001 → 0002 → 0102 → 0202 is illegal because it passes through the deadend 0102.
Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: Turn the last wheel backward once: 0000 → 0009.
Constraints:
- 1 ≤ deadends.length ≤ 500
- Every combination (deadends and target) is a string of exactly 4 digits.
- target is not in deadends.
Hints:
Model it as a graph: every 4-digit combination is a node, and each node has 8 neighbors (4 wheels × 2 directions). "Minimum number of moves" on an unweighted graph means breadth-first search.
Treat deadends exactly like already-visited nodes: never enqueue them. Seed the visited set with the deadends and BFS from "0000".
Two easy-to-miss cases before the search starts: target == "0000" answers 0, and "0000" in deadends answers -1.
To go faster, search from both ends: expand the smaller of two frontiers (from "0000" and from target) until they touch — bidirectional BFS visits far fewer states.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Expected output: 6