Open the Lock
MediumArrayHash TableStringBreadth-First Search
Solution
export function openLock(deadends: string[], target: string): number {
function* next(code: string) {
for (let i = 0; i < code.length * 2; i++) {
const index = Math.floor(i / 2);
const diff = i % 2 === 0 ? -1 : 1;
const nextDigit = (parseInt(code[index]) + diff + 10) % 10;
yield `${code.substring(0, index)}${nextDigit}${code.substring(index + 1)}`;
}
}
const isDeadend = new Set(deadends);
if (isDeadend.has('0000')) {
return -1;
}
let attemptTimes = 0;
let queue: string[] = [target];
while (0 < queue.length) {
const nextQueue: string[] = [];
for (const code of queue) {
if (code === '0000') {
return attemptTimes;
}
for (const nextCode of next(code)) {
if (!isDeadend.has(nextCode)) {
isDeadend.add(nextCode);
nextQueue.push(nextCode);
}
}
}
queue = nextQueue;
attemptTimes += 1;
}
return -1;
}