# [Search] LC 752. Open the Lock

• Given a lock in front of you with 4 circular wheels. Each wheel has 10 slots: `'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`.
• The wheels can rotate freely and wrap around: for example we can turn `'9'` to be `'0'`, or `'0'` to be `'9'`. Each move consists of turning one wheel one slot.
• The lock initially starts at `'0000'`, a string representing the state of the 4 wheels.
• Also given a list of `deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to 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.
`Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"Output: 6Explanation: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".`
`Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"Output: -1Explanation:We can't reach the target without getting stuck.`
• Search + BFS
• Use BFS to explore, in each round we tweak each of the 4 slot by +1 or -1
• Skip (continue) the search when the current string is in deadends or has visited
• A trick to perform the +1 & -1 operations:
`for j in [-1,1]: str((int(curr[i])+j+10)%10)`
• A graph BFS problem to find the shortest path!
• BFS indeed guarantees the shortest path because we are exploring all the available options in each iteration
• Time: O(8*10⁴); 8 = 4*2 because we have 4 slots, and 2 options each search (+1 or -1); 10⁴ because we have 4 slots, and there are 10 possible options in each search
• Space: O(10⁴+D); 10⁴ represents all the possible combinations; with D = size of the deadends array
`class Solution:    def openLock(self, deadends: List[str], target: str) -> int:        start = '0000'        if target == start:            return 0        dead = set(deadends)        if start in dead:            return -1                q = deque([(start, 0)])        v = set(start)                while q:            curr, step = q.popleft()                        for i in range(0,4):                for j in [-1,1]:                    nxt= curr[:i] + str((int(curr[i])+j+10)%10) + curr[i+1:]                     if nxt == target:                        return step+1                    if nxt in dead or nxt in v:                        continue                                        q.append((nxt, step+1))                    v.add(nxt)                return -1`

--

--