79. 单词搜索

---

题目

描述： 给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例： 示例 1:

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出: true

示例 2:

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出: true

示例 3:

输入: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出: false

---

解题思路

核心方法

回溯法（深度优先搜索）：

1. 遍历网格起点：遍历网格中的每个单元格，若单元格的字符与单词的第一个字符相同，则以此为起点启动深度优先搜索。
2. 递归终止条件：
   • 若当前深度等于单词长度，说明已找到完整单词，返回 true。
   • 若当前坐标超出边界、字符不匹配或单元格已被访问，返回 false。
3. 回溯过程：
   • 标记当前单元格为已访问（例如，将字符改为 '#'）。
   • 递归遍历上、下、左、右四个方向的单元格。
   • 若任意方向返回 true，则整体返回 true。
   • 回溯：恢复当前单元格的原始字符，以便其他路径使用。

---

代码实现

回溯法（Java）

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int depth) {
        // 边界与匹配检查
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(depth)) {
            return false;
        }
        // 找到完整单词
        if (depth == word.length() - 1) {
            return true;
        }
        // 标记当前单元格为已访问
        char temp = board[i][j];
        board[i][j] = '#';
        // 遍历四个方向
        boolean res = dfs(board, word, i + 1, j, depth + 1) ||
                      dfs(board, word, i - 1, j, depth + 1) ||
                      dfs(board, word, i, j + 1, depth + 1) ||
                      dfs(board, word, i, j - 1, depth + 1);
        // 回溯：恢复单元格字符
        board[i][j] = temp;
        return res;
    }
}

---

复杂度分析

• 时间复杂度：O(m * n * 3^L)，其中 m 和 n 是网格的行数和列数，L 是单词的长度。每个单元格作为起点时，最多有 3 个方向可探索（排除来时的方向），因此每个起点的时间复杂度为 3^L。
• 空间复杂度：O(L)，递归栈的深度为单词的长度 L，用于存储回溯路径。

---

总结

1. 回溯法通过深度优先搜索和状态回溯，能够高效地在网格中搜索单词。
2. 标记单元格为已访问（如改为 '#'）是避免重复使用的关键，回溯时恢复字符确保了其他路径的正确性。
3. 该方法适用于单词长度较短的场景，若单词过长，时间复杂度会显著增加。

---