79. Word Search

1function exist(board: string[][], word: string): boolean {
2  const total = new Map<string, number>(), need = new Map<string, number>();
3  for (const row of board) for (const ch of row) total.set(ch, (total.get(ch) ?? 0) + 1);
4  for (const ch of word) {
5    need.set(ch, (need.get(ch) ?? 0) + 1);
6    if (need.get(ch)! > (total.get(ch) ?? 0)) return false;
7  }
8  const freq = (ch: string) => total.get(ch) ?? 0;
9  if (freq(word[0]) > freq(word[word.length - 1])) word = [...word].reverse().join("");
10  // ...then the same backtracking search as before
11  const m = board.length, n = board[0].length;
12  function dfs(r: number, c: number, k: number): boolean {
13    if (k === word.length) return true;
14    if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] !== word[k]) return false;
15    const ch = board[r][c];
16    board[r][c] = "#";
17    const ok = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
18    board[r][c] = ch;
19    return ok;
20  }
21  for (let r = 0; r < m; r++)
22    for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true;
23  return false;
24}

Count the letters on the board.

Space: play/pause · ←/→: step