Word Search（单词搜索）

题目 / Problem

中文： 给定一个 m × n 的字符网格 board 和一个字符串 word，如果 word 存在于网格中，返回 true；否则返回 false。

单词必须由水平或垂直相邻的单元格按顺序组成。同一个单元格在一条搜索路径中不能重复使用。

English: Given an m × n grid of characters board and a string word, return true if word exists in the grid; otherwise, return false.

The word must be formed from sequentially adjacent cells. Adjacent cells share a horizontal or vertical edge, and the same cell may not be used more than once in one path.

示例 / Examples

Example 1

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCCED"

Output: true

高亮单元格依次构成 A → B → C → C → E → D。
The highlighted cells form A → B → C → C → E → D in order.

Example 2

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "SEE"

Output: true

Example 3

Input:
board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
word = "ABCB"

Output: false

虽然可以找到 A → B → C，但要继续匹配最后一个 B 必须重复使用之前的 B 单元格，这是不允许的。
Although A → B → C can be found, matching the final B would require reusing the earlier B cell, which is not allowed.

约束 / Constraints

m === board.length
n === board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 只包含大小写英文字母。
board and word contain only lowercase and uppercase English letters.

解题思路：DFS + 回溯 / Approach: DFS + Backtracking

从网格中的每个单元格出发，尝试把它作为 word[0]。如果当前字符匹配，就递归搜索上、下、左、右四个方向，继续匹配下一个字符。
Start from every cell and try it as word[0]. If the character matches, recursively search up, down, left, and right for the next character.

递归函数 dfs(row, column, index) 表示：
The recursive function dfs(row, column, index) asks:

能否从 board[row][column] 开始匹配 word[index...]
Can word[index...] be matched starting at board[row][column]?

递归步骤 / Recursive Steps

如果当前单元格字符不等于 word[index]，返回 false。
If the current cell does not equal word[index], return false.
如果已经匹配到 word 的最后一个字符，返回 true。
If the final character of word has been matched, return true.
临时标记当前单元格为已访问。
Temporarily mark the current cell as visited.
向四个相邻方向递归搜索。
Search recursively in the four adjacent directions.
无论搜索是否成功，都恢复当前单元格的原始字符。
Restore the cell's original character whether the search succeeds or fails.

原地标记与恢复 / In-Place Marking and Restoration

可以把当前字符临时替换为不可能出现在网格中的 '#'：
Temporarily replace the current character with '#', which cannot appear in the board:

const original = board[row][column];
board[row][column] = "#";

// 搜索相邻单元格 / Search neighboring cells

board[row][column] = original;

这样不需要额外创建 visited 矩阵。恢复字符是回溯过程的关键，否则从其他起点开始搜索时会看到被永久修改的网格。
This avoids allocating a separate visited matrix. Restoring the character is essential; otherwise, later searches from other starting cells would see a permanently modified board.

搜索剪枝 / Search Pruning

1. 字符频率检查 / Character-Frequency Check

如果 word 中某个字符出现的次数超过它在 board 中的数量，单词一定不存在，可以直接返回 false。
If any character occurs more often in word than in board, the word cannot exist, so return false immediately.

2. 从更稀有的一端开始 / Start from the Rarer End

如果 word 的最后一个字符在网格中比第一个字符更少，可以反转 word，从更稀有的字符开始搜索。
If the final character of word is rarer in the board than the first, reverse word and begin searching from the rarer character.

这不会改变单词是否存在，因为一条合法路径反向走仍然是合法路径，但可以减少 DFS 起点和分支数量。
This does not change whether the word exists—a valid path remains valid in reverse—but it can reduce the number of DFS starting points and branches.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
function exist(board, word) {
  const rows = board.length;
  const columns = board[0].length;
  const boardFrequency = new Map();

  for (const row of board) {
    for (const character of row) {
      boardFrequency.set(
        character,
        (boardFrequency.get(character) ?? 0) + 1
      );
    }
  }

  const wordFrequency = new Map();

  for (const character of word) {
    const count = (wordFrequency.get(character) ?? 0) + 1;
    wordFrequency.set(character, count);

    if (count > (boardFrequency.get(character) ?? 0)) {
      return false;
    }
  }

  // 从出现次数更少的字符开始，减少搜索分支
  // Start from the rarer end to reduce branching
  if (
    boardFrequency.get(word[0]) >
    boardFrequency.get(word[word.length - 1])
  ) {
    word = [...word].reverse().join("");
  }

  function dfs(row, column, index) {
    if (board[row][column] !== word[index]) {
      return false;
    }

    if (index === word.length - 1) {
      return true;
    }

    const original = board[row][column];
    board[row][column] = "#";

    const found =
      (row > 0 && dfs(row - 1, column, index + 1)) ||
      (row + 1 < rows && dfs(row + 1, column, index + 1)) ||
      (column > 0 && dfs(row, column - 1, index + 1)) ||
      (column + 1 < columns && dfs(row, column + 1, index + 1));

    // 回溯：恢复当前单元格 / Backtrack: restore the cell
    board[row][column] = original;

    return found;
  }

  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (board[row][column] === word[0] && dfs(row, column, 0)) {
        return true;
      }
    }
  }

  return false;
}

执行过程 / Walkthrough

以 word = "ABCCED" 为例，搜索路径为：
For word = "ABCCED", the successful path is:

(0,0) A
  → (0,1) B
  → (0,2) C
  → (1,2) C
  → (2,2) E
  → (2,1) D

每进入一个单元格，就把它暂时标记为 '#'。这样后续递归无法再次匹配同一个位置。返回上一层时再恢复原字符。
Each entered cell is temporarily marked as '#', preventing later recursive calls from reusing it. Its original character is restored while returning to the previous level.

为什么不能只使用一个全局 `visited`？ / Why Not Keep Cells Globally Visited?

“已访问”只针对当前搜索路径。同一个单元格不能在一条路径中重复使用，但可以被其他起点或其他分支使用。
Visited status applies only to the current search path. A cell cannot be reused within one path, but it may be used by another starting point or another branch.

因此，每次递归返回时必须撤销访问标记，而不能永久标记整个搜索过程。
Therefore, the visited mark must be undone during backtracking rather than kept for the entire search.

复杂度 / Complexity

设网格大小为 m × n，单词长度为 L。
Let the board size be m × n and the word length be L.

最坏时间复杂度 / Worst-case time: O(m × n × 4^L)。
Every cell may be a starting point, and each step may explore up to four directions.
由于不能立即返回上一个单元格，更紧的分支估计通常写为 O(m × n × 3^L)，但 O(m × n × 4^L) 是安全的上界。
Since the path cannot immediately return to the previous cell, a tighter branching estimate is often written as O(m × n × 3^L), while O(m × n × 4^L) is a safe upper bound.
辅助空间 / Auxiliary space: O(L)，用于递归调用栈；网格原地标记，不需要额外的 visited 矩阵。
O(L) for the recursion stack; in-place marking avoids a separate visited matrix.
频率映射最多保存英文字母字符，空间相对于网格规模为常数。
The frequency maps contain only English-letter characters and are constant-sized relative to the board.

易错点 / Common Pitfalls

只能水平或垂直移动，不能沿对角线移动。
Move only horizontally or vertically, never diagonally.
同一个单元格在当前路径中只能使用一次。
A cell may be used only once in the current path.
DFS 返回前必须恢复被临时修改的字符，即使已经找到答案也要恢复。
Restore the temporarily modified character before DFS returns, even when a match is found.
每个网格单元格都可能是起点，不能只从左上角开始。
Every board cell may be a starting point; do not search only from the top-left.
大小写字母不同，例如 'A' !== 'a'。
Letter matching is case-sensitive, so 'A' !== 'a'.
'#' 可以作为访问标记，是因为题目保证网格只包含英文字母。
'#' is safe as a visited marker because the board contains only English letters.

Word Search