Open the Lock
Medium · graph traversal
A padlock has four wheels. Each wheel shows a digit from 0 to 9, so the lock shows a four-digit code such as "0472". In one turn you rotate a single wheel one step, either up or down. Turning 9 up gives 0, and turning 0 down gives 9.
The lock starts showing "0000". A list deadends holds codes that jam the lock: as soon as the lock shows one of them, it is stuck and you can no longer turn any wheel.
Return the fewest turns needed to make the lock show target. If it is impossible, return -1. If "0000" itself is in deadends, the lock is stuck from the beginning and the answer is -1, even when target is "0000". If target is in deadends the answer is also -1. If target is "0000" and that code is not jammed, the answer is 0. The list may contain the same code more than once.
Examples
Example 1
Input: deadends = ["0001"], target = "0002"
Output: 4
Turning the last wheel up passes through the jammed code 0001, so go round it: 0010, 0011, 0012, then 0002.
Example 2
Input: deadends = [], target = "1090"
Output: 2
Turn the first wheel up from 0 to 1, and turn the third wheel down from 0 to 9. Both are single turns.
Example 3
Input: deadends = ["0001", "0009", "0010", "0090", "0100", "0900", "1000", "9000"], target = "5555"
Output: -1
Every code one turn from 0000 is jammed, so the lock can never move.
Constraints
- 0 <= len(deadends) <= 1000
- Every code in deadends, and target, is a string of exactly 4 characters, each between '0' and '9'.