Leetcode 752. Open the Lock

Problem

Leetcode 752 - Open the Lock

Example:

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

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

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

Approach

We can use BFS for every digit -1, or 1 to it until we reach the target.

Here is the Python code for the solution:

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if '0000' == target:
            return 0
        
        visit = set(deadends)
        if '0000' in visit:
            return -1
        
        q = deque(['0000'])
        steps = 0

        while q:
            steps += 1
            for _ in range(len(q)):
                lock = curr.popleft()
                for i in range(4):
                    for j in [-1, 1]:
                        digit = str((int(lock[i])+j+10) % 10)
                        nextLock = lock[:i] + digit + lock[i+1:]
                        if nextLock in visit:
                            continue
                        if nextLock == target:
                            return steps
                        q.append(nextLock)
                        visit.add(nextLock)
        
        return -1
    

Time Complexity and Space Complexity

Time Complexity: $O(d^n + m)$ where $d$ is the number of digits (0-9), $n$ is number of wheels, and $m$ is number of deadends

Space Complexity: $O(d^n)$