Description
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0' through '9'. The wheels can rotate freely and wrap around: for example, '9' becomes '0' and '0' becomes '9'. Each move consists of turning one wheel one slot. The lock initially starts at '0000'. You are given a list of deadends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you cannot 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 open the lock, or -1 if it is impossible.
Examples
deadends = ["0201","0101","0102","1212","2002"], target = "0202"6A valid sequence is 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202.
deadends = ["8888"], target = "0009"1Turning the last wheel in reverse moves from 0000 to 0009, reaching the target in one step.
deadends = ["0000"], target = "8888"-1The starting position 0000 is itself a deadend, so the lock cannot be opened at all.
Constraints
- •
1 ≤ deadends.length ≤ 500 - •
deadends[i].length == 4 - •
target.length == 4 - •
target will not be in the list of deadends - •
target and deadends[i] consist of digits only