A lock has 4 rotating dials with digits from
0 to 9. Each dial can be rotated up or down. The lock starts at "0000", you are given target and a list of deadends forbidden combinations. Return the minimum number of turns to open the lock, or -1 if impossible.Example 1
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: From `0000`, you can turn the last digit down once to get `0009` immediately.
Output: 1
Explanation: From `0000`, you can turn the last digit down once to get `0009` immediately.
Example 2
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: The shortest path to the target while avoiding forbidden combinations has length 6.
Output: 6
Explanation: The shortest path to the target while avoiding forbidden combinations has length 6.