This content originally appeared on DEV Community and was authored by seanpgallivan
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
10slots:'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
deadendsdead 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
targetrepresenting the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or-1if 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 <= 500deadends[i].length == 4target.length == 4targetwill not be in the listdeadends.targetanddeadends[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;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-06-04T09:49:29+00:00) Solution: Open the Lock. Retrieved from https://www.scien.cx/2021/06/04/solution-open-the-lock/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.