022-单词搜索（回溯法）

单词搜索（Word Search）

给定一个 m x n 的二维字符网格 board 和一个字符串 word，判断 word 是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格（水平或垂直相邻）构成，同一个单元格内的字母不允许被重复使用。

示例

输入：
board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
],
word = "ABCCED"

输出：true
解释：路径 A → B → C → C → E → D 可以构成单词 "ABCCED"。

---

方法：回溯法（DFS + 剪枝）

核心思想

1. 遍历网格：对每个单元格作为起点，尝试匹配 word 的第一个字符。
2. DFS 回溯：
   • 从当前单元格出发，向 上、下、左、右 四个方向递归搜索。
   • 如果当前字符匹配，继续搜索下一个字符；否则回溯。
3. 避免重复使用：用 visited 矩阵或临时修改 board 标记已访问的单元格。

JavaScript 代码

var exist = function(board, word) {
    const m = board.length;
    const n = board[0].length;
    
    const dfs = (i, j, index) => {
        if (index === word.length) return true; // 全部匹配完成
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[index]) {
            return false; // 越界或不匹配
        }
        
        const temp = board[i][j]; // 临时存储当前字符
        board[i][j] = '#';        // 标记为已访问（避免重复使用）
        
        // 向四个方向搜索
        const found = dfs(i + 1, j, index + 1) ||
                     dfs(i - 1, j, index + 1) ||
                     dfs(i, j + 1, index + 1) ||
                     dfs(i, j - 1, index + 1);
        
        board[i][j] = temp; // 恢复原始字符（回溯）
        return found;
    };
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true; // 从 (i,j) 开始匹配
        }
    }
    return false;
};

时间复杂度

• 最坏情况：O(m × n × 4^L)，其中 L 是 word 的长度（每个单元格有 4 个方向的选择）。
• 剪枝优化：实际运行时，不匹配的路径会提前终止。

---

关键点

1. 递归终止条件：
   • index === word.length：成功匹配整个单词。
   • 越界或字符不匹配：直接返回 false。
2. 避免重复访问：
   • 临时修改 board[i][j] 为特殊字符（如 #），递归结束后恢复。
3. 方向搜索：
   • 每次递归尝试 上、下、左、右 四个方向。

---

示例解析

以输入 board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] 和 word = "ABCCED" 为例：

1. 从 (0,0) 开始（A 匹配 word[0]）：
   • 向下到 (1,0)（S ≠ B）→ 回溯。
   • 向右到 (0,1)（B 匹配 word[1]）：
     • 继续向右到 (0,2)（C 匹配 word[2]）：
       • 向下到 (1,2)（C 匹配 word[3]）：
         • 向下到 (2,2)（E 匹配 word[4]）：
           • 向左到 (2,1)（D 匹配 word[5]）→ 返回 true。

---

变种问题

单词搜索 II（多个单词）

给定一个 board 和一个单词列表 words，返回所有能在 board 中匹配的单词。
优化方法：使用 Trie 树（字典树） 预处理 words，结合回溯法。

允许重复使用单元格

若允许重复使用单元格，需调整 visited 逻辑（一般不常见）。

---

总结

方法	时间复杂度	空间复杂度	适用场景
回溯法（DFS）	O(m × n × 4^L)	O(L)（递归栈）	通用
Trie + 回溯	O(m × n × 4^L)	O(T)（Trie 节点数）	多单词搜索

推荐：

• 单单词搜索直接用回溯法。
• 多单词搜索用 Trie 优化。