[Search] LC 752. Open the Lock

Goals

• 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.

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 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Strategy

• 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)

Highlight

• 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

Complexity

• 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

Code

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