[Leetcode] Open the Lock
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 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 -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 cannot reach the target without getting stuck.
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.
How to understand?
To get the shortest path numbers from 0000 to the target , find the all the possible path from 0000 to the target digits. Use BFS to find the all the possible combinations from the previous one, and also check the deadends since it can't go that path to unlock the lock. Return the how many turns took when it reaches the target.
How to approach?
BFS, queue
function openLock(deadends: string[], target: string): number {
const visited = new Set(deadends);
const queue: [string, number][] = [["0000", 0]];
function children(lock: string): string[] {
const res: string[] = [];
for (let i = 0; i < 4; i++) {
const digit = parseInt(lock[i]);
const increment = (digit + 1) % 10;
const decrement = (digit + 9) % 10; // same as (digit - 1 + 10) % 10
res.push(lock.slice(0, i) + increment + lock.slice(i + 1));
res.push(lock.slice(0, i) + decrement + lock.slice(i + 1));
}
return res;
}
while (queue.length > 0) {
const [lock, turns] = queue.shift()!;
if (lock === target) return turns;
for (const child of children(lock)) {
if (!visited.has(child)) {
visited.add(child);
queue.push([child, turns + 1]);
}
}
}
return -1;
}
- create Set to check if the combination is already visited, it includes deadends' combinations when intialize the value.
- and create the queue to store the locks and turns in a pair and initialize it with 0000 and 0 since it is a starting point.
- while loop to check all the items in the queue.
- take the first item in the queue and check lock if it is the target then return the turns.
- and the generate all the possible child from the current lock by using children function and check if the child is already visited using Set and if it is not visited yet, then add it to the set and also push it to the queue with +1 turns since it take 1 more turn to reach there.
- and if there is no item to check in the queue, then return -1, that means there is no way to reach to the target avoiding deadends.
- children function will create +1 -1 for all the digits in the lock.
- take the digit and calculate them and add it to the res and return the res.
summary
Use BFS to find all the possible combinations of lock and check it in the deadends if it is not allowed to go that path then avoid it and find the shortest path number to reach there. Think of it as layer by layer in the 4 digits lock, expand the boundary in the 4 combinations while not reaching deadends to find the target lock.