752.打开转盘锁

链接：752.打开转盘锁
难度：Medium
标签：广度优先搜索、数组、哈希表、字符串
简介：字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

题解 1 - typescript

• 编辑时间：2021-06-26
• 执行用时：776ms
• 内存消耗：56.8MB
• 编程语言：typescript
• 解法介绍：广度优先搜索，储存后进行遍历。

function openLock(deadends: string[], target: string): number {
  const prevMap: Record<string, string> = {
    0: '9',
    1: '0',
    2: '1',
    3: '2',
    4: '3',
    5: '4',
    6: '5',
    7: '6',
    8: '7',
    9: '8',
  };
  const nextMap: Record<string, string> = {
    0: '1',
    1: '2',
    2: '3',
    3: '4',
    4: '5',
    5: '6',
    6: '7',
    7: '8',
    8: '9',
    9: '0',
  };
  const INIT_STR = '0000';
  const set = new Set(deadends);
  if (set.has(INIT_STR)) return -1;
  if (target === INIT_STR) return 0;
  const queue = [INIT_STR];
  const map = new Map<string, number>([[INIT_STR, 0]]);
  let ans = Infinity;
  const updateQueue = (str: string, index: number, dict: Record<string, string>, step: number) => {
    const replaceStr = str.substring(0, index) + dict[str[index]] + str.substring(index + 1);
    if (replaceStr === target) {
      ans = Math.min(ans, step + 1);
      return;
    }
    if (!set.has(replaceStr)) {
      map.has(replaceStr) || queue.push(replaceStr);
      map.set(replaceStr, Math.min(map.get(replaceStr) ?? Infinity, step + 1));
    }
  };
  while (queue.length !== 0) {
    const str = queue.shift()!;
    const step = map.get(str)!;
    for (let i = 0; i < 4; i++) {
      updateQueue(str, i, prevMap, step);
      updateQueue(str, i, nextMap, step);
    }
  }
  return ans === Infinity ? -1 : ans;
}

题解 2 - typescript

• 编辑时间：2021-07-25
• 执行用时：200ms
• 内存消耗：49.1MB
• 编程语言：typescript
• 解法介绍：bfs。

function openLock(deadends: string[], target: string): number {
  const headendSet = new Set(deadends);
  if (headendSet.has('0000')) return -1;
  const queue: [string, number][] = [['0000', 0]];
  const set = new Set<string>(['0000']);
  const getNext = (num: number) => (num + 1) % 10;
  const getPrev = (num: number) => (num === 0 ? 10 : num) - 1;
  const add = (str: string, count) => {
    if (set.has(str) || headendSet.has(str)) return;
    set.add(str);
    queue.push([str, count]);
  };
  while (queue.length) {
    const [str, count] = queue.shift()!;
    if (str === target) return count;
    for (let i = 0; i < 4; i++) {
      const num = str.codePointAt(i)! - '0'.codePointAt(0)!;
      add(str.substr(0, i) + getNext(num) + str.substr(i + 1), count + 1);
      add(str.substr(0, i) + getPrev(num) + str.substr(i + 1), count + 1);
    }
  }
  return -1;
}