Day 4: Open the Lock

Problem Link:

Explore - LeetCode

Problem Statement:

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 '0', or '0' to be '9'. Each move consists of turning one wheel in 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.

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

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.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

Constraints:

- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target will not be in the list deadends
- target and deadends[i] consist of digits only.Output: -1

My Solution:

from collections import deque
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if target in deadends or '0000' in deadends or not target:
            return -1
        
        deadset = set(deadends)
        queue = deque(['0000'])
        distance = {'0000': 0}
        
        while queue:
            cur = queue.popleft()
            if cur == target:
                return distance[target]
            
            for neigh in self.neighbours(cur, deadset):
                if neigh in distance:
                    continue
                queue.append(neigh)
                distance[neigh] = distance[cur] + 1
                
        return -1
    
    def neighbours(self, state, deadset):
        ans = []
        for idx, char in enumerate(state):
            for op in [-1, 1]:
                nextSlot = str((int(char) + op) % 10) 
                neighbour = state[:idx] + nextSlot + state[idx + 1:]
                if neighbour not in deadset:
                    ans.append(neighbour)
        return ans

Explanation:

Let’s take a simple example first.

deadends = ["3"], target = "5", initialString = "0"

If this was the case, then we have two options, either go from 1 to 5 clockwise or anticlockwise. Notice that if we move clockwise, we will be stuck at the dead-end 3. So, to solve this, we will have to come up with an idea where we can check clockwise and anticlockwise simultaneously. A queue is the best option for such a problem.

Let’s see how.

1. Push 0 into the queue and mark it as level 0. Along with a queue, keep a visited array.
2. Pop 0, add it to the visited array, push both neighbors i.e. 1(clockwise) and 9(anti-clockwise) into the queue.
3. Pop 1, add it to the visited array. Now we have two options i.e. 0 and 2. We discard 0 as it was already in the visited array. Also, pop 9. Again we have two options i.e. 0 and 8. Repeat the same steps until you reach the target.
4. Note that at level 2, when we pop 2, we have an option of pushing 3 to the queue but since it was a dead-end, we skip it.

Hence, we get the target in 5 steps.

In the same manner, work out this algorithm for the given question. The change is that instead of 1 digit we have 4 digits. So, apply this algorithm for all the digits and you will reach the answer.

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!