Solution: Open the Lock
Tags: algorithms, javascript, java, python
Published: 2021-06-04 09:49:29

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/open-the-lock/discuss/1250681).*

---

#### [Leetcode Problem #752 (*Medium*): Open the Lock](https://leetcode.com/problems/open-the-lock/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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".<br>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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```