Solution: Open the Lock

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode’s forums.

Leetcode Problem #752 (Medium): Open the Lock

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode’s forums.



Leetcode Problem #752 (Medium): Open the Lock



Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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



Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

There are 10^4 combinations for the lock, and we can think of each one as a node on a graph. We then have to find the shortest path from “0000” to the target combination without going through one of the deadends.

In a normal problem dealing with a shortest path on a graph, we keep track of previously visited nodes in a boolean array of combinations (seen), so we can just go ahead and add all of the deadends into seen by converting the strings to numbers.

Then, we can solve the shortest path problem with a standard queue. We’ll have an outer loop to keep track of the number of turns we’ve taken, while the inner loop will run the length of the current turn (qlen).

On each turn, we’ll take the current queue entry (curr), then we’ll iterate through the four digits and create both a mask for that digit as well as a masked version of curr. (For example, if curr = 4213 and we’re on the 2nd digit, mask would be 1 and masked would be 4203.) This way we can change the mask and add it back to masked to form the next combination. For each digit, we’ll also have to attempt both the forward and backward move, so we can add 1 and then 9 to the mask, before applying modulo 10, to get the new values.

For each next combination, if it’s our target we should return turns, and if it’s been seen, we should continue to the next iteration. Otherwise, we should consider it seen and add it to the queue. If we ever completely empty the queue, then there are no more possible moves, so we should return -1.

We also need to remember to account for edge cases where “0000” is either a deadend or the target.

  • Time Complexity: O(1e4) or O(1) because there are always a maximum of 1e4 possible combinations
  • Space Complexity: O(2e4) or O(1) for seen and the maximum length of the queue



Javascript Code:

(Jump to: Problem Description || Solution Idea)

var openLock = function(deadends, target) {
    if (target === "0000") return 0
    let queue = [0], seen = new Uint8Array(10000)
    for (let d of deadends)
        seen[~~d] = 1
    target = ~~target
    if (seen[0]) return -1
    for (let turns = 1; queue.length; turns++) {
        let qlen = queue.length
        for (let i = 0; i < qlen; i++) {
            let curr = queue.shift()
            for (let j = 1; j < 10000; j *= 10) {
                let mask = ~~(curr % (j * 10) / j),
                    masked = curr - (mask * j)
                for (let k = 1; k < 10; k += 8) {
                    let next = masked + (mask + k) % 10 * j
                    if (seen[next]) continue
                    if (next === target) return turns
                    seen[next] = 1
                    queue.push(next)
                }
            }
        }
    }
    return -1
};



Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        if target == "0000": return 0
        queue, target = deque([0]), int(target)
        seen, turns = [0] * 10000, 1
        for d in deadends: seen[int(d)] = 1
        if seen[0]: return -1
        while len(queue):
            qlen = len(queue)
            for i in range(qlen):
                curr, j = queue.popleft(), 1
                while j < 10000:
                    mask = curr % (j * 10) // j
                    masked = curr - (mask * j)
                    for k in range(1,10,8):
                        nxt = masked + (mask + k) % 10 * j
                        if seen[nxt]: continue
                        if nxt == target: return turns
                        seen[nxt] = 1
                        queue.append(nxt)
                    j *= 10
            turns += 1
        return -1



Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int openLock(String[] deadends, String target) {
        if (target.equals("0000")) return 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        boolean[] seen = new boolean[10000];
        for (String el : deadends)
            seen[Integer.parseInt(el)] = true;
        int targ = Integer.parseInt(target);
        if (seen[0]) return -1;
        for (int turns = 1; !queue.isEmpty(); turns++) {
            int qlen = queue.size();
            for (int i = 0; i < qlen; i++) {
                int curr = queue.poll();
                for (int j = 1; j < 10000; j *= 10) {
                    int mask = curr % (j * 10) / j,
                        masked = curr - (mask * j);
                    for (int k = 1; k < 10; k += 8) {
                        int next = masked + (mask + k) % 10 * j;
                        if (seen[next]) continue;
                        if (next == targ) return turns;
                        seen[next] = true;
                        queue.add(next);
                    }
                }
            }
        }
        return -1;
    }
}



C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if (target == "0000") return 0;
        queue<int> queue;
        queue.push(0);
        bool seen[10000]{false};
        for (auto& d : deadends)
            seen[stoi(d)] = true;
        int targ = stoi(target);
        if (seen[0]) return -1;
        for (int turns = 1; queue.size(); turns++) {
            int qlen = queue.size();
            for (int i = 0; i < qlen; i++) {
                int curr = queue.front();
                queue.pop();
                for (int j = 1; j < 10000; j *= 10) {
                    int mask = curr % (j * 10) / j,
                        masked = curr - (mask * j);
                    for (int k = 1; k < 10; k += 8) {
                        int next = masked + (mask + k) % 10 * j;
                        if (seen[next]) continue;
                        if (next == targ) return turns;
                        seen[next] = true;
                        queue.push(next);
                    }
                }
            }
        }
        return -1;
    }
};

Print Share Comment Cite Upload Translate
APA
seanpgallivan | Sciencx (2024-03-29T09:03:16+00:00) » Solution: Open the Lock. Retrieved from https://www.scien.cx/2021/06/04/solution-open-the-lock/.
MLA
" » Solution: Open the Lock." seanpgallivan | Sciencx - Friday June 4, 2021, https://www.scien.cx/2021/06/04/solution-open-the-lock/
HARVARD
seanpgallivan | Sciencx Friday June 4, 2021 » Solution: Open the Lock., viewed 2024-03-29T09:03:16+00:00,<https://www.scien.cx/2021/06/04/solution-open-the-lock/>
VANCOUVER
seanpgallivan | Sciencx - » Solution: Open the Lock. [Internet]. [Accessed 2024-03-29T09:03:16+00:00]. Available from: https://www.scien.cx/2021/06/04/solution-open-the-lock/
CHICAGO
" » Solution: Open the Lock." seanpgallivan | Sciencx - Accessed 2024-03-29T09:03:16+00:00. https://www.scien.cx/2021/06/04/solution-open-the-lock/
IEEE
" » Solution: Open the Lock." seanpgallivan | Sciencx [Online]. Available: https://www.scien.cx/2021/06/04/solution-open-the-lock/. [Accessed: 2024-03-29T09:03:16+00:00]
rf:citation
» Solution: Open the Lock | seanpgallivan | Sciencx | https://www.scien.cx/2021/06/04/solution-open-the-lock/ | 2024-03-29T09:03:16+00:00
https://github.com/addpipe/simple-recorderjs-demo