#752
Open the Lock
specialist · 690 · lc medium +30 · verified · 61.2% accepted · 5,118 likes · top 61%
Description
A combination lock has four circular wheels each ranging from '0' to '9' and wrapping around at both ends. The lock starts at '0000' and each move turns exactly one wheel by one slot in either direction.
Certain codes in deadends are forbidden: landing on one freezes the lock. Given a target code, return the minimum number of moves to reach it from '0000', or -1 if it is unreachable.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".
Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.
Code
1
2
3