488.祖玛游戏

链接：488.祖玛游戏
难度：Hard
标签：栈、广度优先搜索、记忆化搜索、字符串、动态规划
简介：给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。

题解 1 - typescript

• 编辑时间：2021-11-09
• 执行用时：800ms
• 内存消耗：64.7MB
• 编程语言：typescript
• 解法介绍：dfs。

function format(board: string): string {
  let flag = false;
  let n = board.length;
  do {
    flag = false;
    for (let i = 0; i < n - 1; i++) {
      const ball = board[i];
      let end = i;
      let cnt = 1;
      while (end < n - 1 && ball === board[end + 1]) {
        end++;
        cnt++;
      }
      if (cnt < 3) {
        i = end;
        continue;
      }
      board = board.substring(0, i) + board.substring(end + 1);
      n = board.length;
      flag = true;
    }
  } while (flag);
  return board;
}
function findMinStep(board: string, hand: string): number {
  const cache: Record<string, number> = {};
  const map: Record<string, number> = { R: 0, Y: 0, B: 0, G: 0, W: 0 };
  for (const ball of hand) map[ball]++;
  return dfs(board, 0, map);
  function dfs(board: string, cnt: number, map: Record<string, number>): number {
    if (cache[board]) return cache[board];
    if (board === '') return cnt;
    const n = board.length;
    const list = Object.entries(map)
      .filter(([, v]) => v > 0)
      .map(([k]) => k);
    let ans = Infinity;
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < list.length; j++) {
        const ball = list[j];
        map[ball]--;
        const nextBoard = board.substring(0, i) + ball + board.substring(i);
        const res = dfs(format(nextBoard), cnt + 1, map);
        if (res !== -1) ans = Math.min(ans, res);
        map[ball]++;
      }
    }
    return (cache[board] = ans === Infinity ? -1 : ans);
  }
}