Leetcode 752. Open the Lock

Problem Explanation:

You have a 4-wheel combination lock where each wheel has digits from 0 to 9. You can rotate the wheel up or down to change the digits. The lock starts at "0000". There are a few combinations which are dead ends meaning if you reach those combinations, your lock will become unresponsive and you won't be able to open it anymore.

Your task is to find the least amount of wheel rotations needed to reach the target combination. If it is not possible to reach the target without hitting a dead end, the function should return -1.

For example, if we have deadends ["8887","8889","8878","8898","8788","8988","7888","9888"] and target "8888" We can not reach to 8888 without hitting a deadend so this case will return -1.

Approach Explanation:

Here the approach could be using Breadth First Search (BFS). The reason why we choose BFS is because it will help us to look at all possibilities one step away then two steps away and so on until we reach our target combination. As we want to find the minimal steps to reach the target, BFS is the best choice.

  1. Create two sets: dead and visited, fill set dead with deadends.

  2. First, we have to check if lock in its start position (0000) is in dead or target is the start itself, in both cases we stop and return -1 or 0 respectively.

  3. Then we enqueue the start position into the queue.

  4. Start BFS, for each code dequeued from the queue, we visit each possible state that we can reach in one step by rotating one wheel forwards or backwards. For each possible state:

    • Continue to next possible state if it is in dead or this state has already been visited.

    • Push it to the queue and mark visited now as it has entered the queue. It will not be changed in the future.

    • Return step => the best we can use here is a class member so no need to carry it throughout BFS. If the new state is equal to the target.

  5. If BFS has finished and found no solution, return -1.

To get more clear, let's take a scenario:

For example, we have deadends ["0201","0101","0102","1212","2002"] and target "0202"

From 0000, we can go to 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202. We deliberately avoid 0102 as it's marked as a deadend. So, we reach target in 6 steps.

Python Solution:

1
2python
3from collections import deque
4class Solution:
5    def openLock(self, deadends: List[str], target: str) -> int:
6        if '0000' in deadends: return -1
7        if target == '0000': return 0
8
9        def neighbors(node:str) -> List[str]:
10            res = []
11            for i in range(4):
12                n = int(node[i])
13                for d in [1, -1]:
14                    y = (n + d) % 10
15                    res.append(node[:i]+str(y)+node[i+1:])
16            return res
17
18        dead_ends = set(deadends)
19        queue = deque([('0000', 0)])
20        while queue:
21            node, depth = queue.popleft()
22            if node == target: return depth
23            if node in dead_ends: continue
24            dead_ends.add(node)   # mark node as visited
25            for nei in neighbors(node):
26                if not nei in dead_ends:
27                    queue.append((nei, depth + 1))
28
29        return -1

In the above python program, we first import the deque from collections. It helps to keep all pending moves that possible from the current lock state. We then define a helper function named neighbors which returns all possible movements from the current state. Inside the main function, we first check if '0000' is in the deadends or if '0000' is our target, we return -1 or 0 accordingly.

The we start BFS and for each node dequeued from queue, if it's the target, we return the depth which is the step we are on. If it's a deadend, we skip to the next node. If it hasn't been visited, we add its possible states to the queue and add it to our visited nodes. If no solution is found after BFS, we return -1.

Java Solution:

1
2java
3class Solution {
4    public int openLock(String[] deadends, String target) {
5        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
6        Queue<String> queue = new LinkedList<>();
7        
8        if (dead.contains("0000")) return -1;
9        if ("0000".equals(target)) return 0;
10        
11        queue.offer("0000");
12        Set<String> visited = new HashSet<>(Arrays.asList("0000"));
13
14        for (int steps = 1; steps < 10000; steps++) {
15            for (int s = queue.size(); s > 0; s--) {
16                String node = queue.poll();
17                for (String nei : neighbors(node)) {
18                    if (nei.equals(target)) return steps;
19                    if (!dead.contains(nei) && visited.add(nei)) queue.offer(nei);
20                }
21            }
22        }
23        return -1;
24    }
25
26    private String[] neighbors(String node) {
27        String[] result = new String[8];
28        char[] chars = node.toCharArray();
29        for (int i = 0; i < 4; i++) {
30            char o = chars[i];
31            chars[i] = (char) (((o - '0') + 1) % 10 + '0');
32            result[i*2] = new String(chars);
33            chars[i] = (char) (((o - '0') + 9) % 10 + '0');
34            result[i*2+1] = new String(chars);
35            chars[i] = o;
36        }
37        return result;
38    }
39}

The Java solution is simillar to the python one. The main difference is in defining and adding elements to the queue. Also Java lacks a built-in method to manipulate a specific character in a string. So, we have to convert it to a char array first before we can modify it. Then, after the modification, we convert the char array back to a string.

Javascript Solution:

1
2javascript
3var openLock = function(deadends, target) {
4    let start = '0000';
5    if (start === target) return 0;
6    
7    let dead = new Set(deadends);
8    if (dead.has(start)) return -1;
9
10    let q = [start];
11    let level = 0;
12    let visited = new Set([start]);
13    
14    while (q.length > 0) {
15        let newQ = [];
16        level++;
17        for (let node of q) {
18            let arr = node.split('');
19            for (let i = 0; i < 4; i++) {
20                for (let d = -1; d <= 1; d += 2) {
21                    let old = arr[i];
22                    arr[i] = String((Number(arr[i]) + d + 10) % 10);
23                    let next = arr.join('');
24                    if (!dead.has(next)) {
25                        if (next === target) return level;
26                        if (!visited.has(next)) {
27                            newQ.push(next);
28                            visited.add(next);
29                        }
30                    }
31                    arr[i] = old;
32                }
33            }
34        }
35        q = newQ;
36    }
37    return -1;
38};

In the javascript solution, we follow the same approach, but in JavaScript, to set a specific character in a string, we first need to convert the string to an array, perform the change, then join the array back to a string.

This solution explained above is very elegant, fast (BFS for 8-branch tree, 8 is the maximum number of neighbours), space efficient and uses a nice trick of adding neighbours to avoid cycling in the graph. Each function in the provided solutions adhere to the problem constraints and utilise the BFS approach. They keep track of the deadends and already visited combinations to avoid traversing those parts of the tree again. They also increment the required steps at each level and check all neighbours of a node before moving on.

Let's understand each solution individually:

Python Solution:

In Python, we have collections.deque() which gives us an efficient way of dequeuing and enqueuing elements. We first check if starting point '0000' is a deadend, or if it is our target, in those cases we return -1 or 0 as per problem constraints.

Then, we add it to the queue and start BFS. For each node dequeued from queue, we generate its neighbors i.e., all possible combination by rotating dials one step, and if it's the target, we return the step we are on. If it's a deadend, we skip to the next node. If it hasn't been visited, we add it to queue and deadends.

1
2python
3from collections import deque
4
5def openLock(deadends, target):
6    dead = set(deadends)
7    queue = deque([('0000', 0)])
8    visited = {'0000'}
9
10    while queue:
11        node, depth = queue.popleft()
12        if node == target:
13            return depth
14        if node in dead:
15            continue
16        for i in range(4):
17            for d in [-1, 1]:
18                nei = node[:i] + str((int(node[i]) + d) % 10) + node[i+1:]
19                if nei not in visited:
20                    visited.add(nei)
21                    queue.append((nei, depth + 1))
22    return -1

Java Solution:

In Java, we use HashSet for keeping track of deadends and visited nodes, and LinkedList as the queue for BFS. The rest of the logic follows the same as Python solution.

1
2java
3import java.util.*;
4
5class Solution {
6    public int openLock(String[] deadends, String target) {
7        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
8        Queue<String> queue = new LinkedList<>();
9        queue.offer("0000");
10        Set<String> visited = new HashSet<>();
11        visited.add("0000");
12        int depth = 0;
13
14        while(!queue.isEmpty()) {
15            int size = queue.size();
16            while (size > 0) {
17                String node = queue.poll();
18                if (node.equals(target)) {
19                    return depth;
20                }
21                if (dead.contains(node)) {
22                    size--;
23                    continue;
24                }
25                StringBuilder sb = new StringBuilder(node);
26                for (int i = 0; i < 4; i++) {
27                    char c = sb.charAt(i);
28                    String s1 = sb.substring(0, i) + (c=='9' ? 0 : c-'0'+1) + sb.substring(i+1);
29                    String s2 = sb.substring(0, i) + (c=='0' ? 9 : c-'0'-1) + sb.substring(i+1);
30
31                    if (!visited.contains(s1) && !dead.contains(s1)) {
32                        queue.offer(s1);
33                        visited.add(s1);
34                    }
35                    if (!visited.contains(s2) && !dead.contains(s2)) {
36                        queue.offer(s2);
37                        visited.add(s2);
38                    }
39                }
40                size--;
41            }
42            depth++;
43        }
44        return -1;
45    }
46}

JavaScript Solution:

In JavaScript, we use Set for keeping track of deadends and visited nodes, and an Array as the queue for BFS. The logic follows the same as Python solution.

1
2javascript
3var openLock = function(deadends, target) {
4    let dead = new Set(deadends);
5    let q = ["0000"];
6    let visited = new Set(q);
7    let steps = 0;
8
9    while (q.length > 0) {
10        let newQ = [];
11        for (let node of q) {
12            if (node === target) {
13                return steps;
14            }
15            if (dead.has(node)) {
16                continue;
17            }
18            for (let i = 0; i < 4; i++) {
19                for (let dir of [-1, 1]) {
20                    let arr = node.split('');
21                    arr[i] = ((Number(arr[i]) + dir + 10) % 10).toString();
22                    let nei = arr.join('');
23                    if (!visited.has(nei)) {
24                        newQ.push(nei);
25                        visited.add(nei);
26                    }
27                }
28            }
29        }
30        q = newQ;
31        steps++;
32    }
33    return -1;
34};

These solutions provide an efficient way for solving this problem using the BFS approach and a bit of handling for strings of numbers for the combinations.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫