Leetcode 752 - Open the Lock

Problem Description

You have 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.

You are 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.

Examples

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 2

Input: deadends = ["8888"], target = "0009"

Output: 1

Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

Thought Process / Intuition

The problem requires us to find the shortest number of turns required to reach the target. In order to find the shortest number of turns, we should use BFS. Each node will have up to 8 edges, as each wheel is able to +1 or -1, as long as it's not in the deadlocks and not been visited. As such, we can initialise the visited set along with the deadlocks.`

Approach

First, check if '0000' is in deadends or the target, so we can instantly return the solution.
Initialise a counter variable to 0
Initialize a queue with the initial wheel state of '0000'.
Begin BFS, adding the children of each wheel state to the queue. Adjust the up and down accordingly, and only add if + its not in visited.
If we find the target, we return counter +1.
If we finish BFS and we have not returned the solution, it does not exist. Therefore we return -1

Solution

from collections import deque
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if '0000' in deadends:
            return -1
        if '0000' == target:
            return 0
        queue = deque([list('0000')])
        counter = 0
        visited = set(deadends)
        while len(queue) > 0:
            n = len(queue)
            for _ in range(n):
                lock = queue.popleft()
                for i in range(4):
                    up = ord(lock[i]) + 1
                    down = ord(lock[i]) - 1
                    if up > 57 and down < 48:
                        lock_copy = lock[:]
                        lock_copy[i] = '0'
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                        lock_copy = lock[:]
                        lock_copy[i] = '9'
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                    elif up > 57:
                        lock_copy = lock[:]
                        lock_copy[i] = '0'
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                        lock_copy = lock[:]
                        lock_copy[i] = chr(down)
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                    elif down < 48:
                        lock_copy = lock[:]
                        lock_copy[i] = chr(up)
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                        lock_copy = lock[:]
                        lock_copy[i] = '9'
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                    else:
                        lock_copy = lock[:]
                        lock_copy[i] = chr(up)
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
                        lock_copy = lock[:]
                        lock_copy[i] = chr(down)
                        if ''.join(lock_copy) == target:
                            counter += 1
                            return counter
                        if ''.join(lock_copy) not in visited:
                            queue.append(lock_copy)
                            visited.add(''.join(lock_copy))
            counter += 1
        return -1

Complexity Analysis

Time complexity: $O(b^d)$

Time complexity is $O(b^d)$ , where b is branching factor (upper bounded by 8), and d is depth of the tree, which is $log(10^4)$ , where $10^4$ is simply the number of possible nodes, and we use that to calcualte the hieght of the tree.

Space complexity: $O(2*10^4)$

Space complexity includes the space required for the visited set as well as the queue, so just 2 x number of nodes.
Space complexity is $O(2*10^4)$
Essentially, $O(1)$ , but to be accurate, it's $O(2*10^4)$

Shoutout to My Friends' Solutions

Kurt's Solution

Si Yuan's Solution

My Solution on Leetcode