我们来讲解 LeetCode 第 79 题：单词搜索（Word Search）。

1. 题目描述

给定一个 m x n 的二维字符网格 board 和一个字符串单词 word。
要求：在网格中找出是否存在单词 word，单词必须按照字母顺序，通过相邻的单元格（相邻指上下左右相邻）内的字母构成，同一个单元格内的字母不允许被重复使用。

示例

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

输出：true

2. 思路分析

这个问题是典型的二维平面上的回溯搜索（DFS + 回溯）问题。
核心点：

• 遍历网格的每个格子作为起点。
• 从起点开始，进行深度优先搜索（DFS），尝试匹配单词的每个字符。
• 如果当前字符匹配，继续向四个方向（上、下、左、右）搜索下一个字符。
• 如果某个方向最终能匹配完整单词，返回 true；否则回溯（恢复访问标记，尝试其他方向）。
• 注意不能重复使用同一个格子，所以需要标记已访问的格子，回溯时撤销标记。

3. 算法步骤

1. 遍历每个格子
   对 board 中每个 (i, j) 作为搜索起点，调用 DFS 函数。

2. DFS 函数设计

   • 参数：当前坐标 (i, j)，当前匹配到单词的第几个字符 index。
   • 终止条件：
     • 如果 index == len(word)，说明全部匹配成功，返回 true。
     • 如果越界或当前字符不匹配，返回 false。
   • 标记当前格子已访问（例如临时修改 board[i][j] 为特殊字符如 '#'，避免重复使用）。
   • 向四个方向递归搜索 (i+1, j)、(i-1, j)、(i, j+1)、(i, j-1)。
   • 如果四个方向有一个返回 true，则最终结果为 true。
   • 回溯：恢复 board[i][j] 为原字符。
   • 返回最终结果。

3. 主函数
   如果任意起点 DFS 返回 true，则整体返回 true；否则返回 false。

4. 详细代码实现（Python）

def exist(board, word):
    if not board or not word:
        return False
    
    m, n = len(board), len(board[0])
    
    def dfs(i, j, index):
        # 全部匹配成功
        if index == len(word):
            return True
        # 越界或字符不匹配
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[index]:
            return False
        
        # 标记已访问
        temp = board[i][j]
        board[i][j] = '#'
        
        # 四个方向搜索
        found = (dfs(i+1, j, index+1) or
                dfs(i-1, j, index+1) or
                dfs(i, j+1, index+1) or
                dfs(i, j-1, index+1))
        
        # 回溯，恢复字符
        board[i][j] = temp
        
        return found
    
    # 遍历每个起点
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True
    return False

5. 复杂度分析

• 时间复杂度：最坏情况是遍历整个网格（m*n）并对每个起点进行 DFS（四个方向，深度为单词长度 L），但通过剪枝（不匹配时立即返回），实际不会达到完全的 O(m*n*4^L)，但理论上最坏情况是 O(m*n*4^L)。
• 空间复杂度：主要是递归栈的深度，最大深度为 L（单词长度），所以是 O(L)。

6. 关键点总结

• 使用 DFS 进行二维平面搜索。
• 利用回溯法标记和恢复访问状态，避免额外空间。
• 剪枝：一旦发现不匹配立即返回，减少不必要的搜索。
• 四个方向的搜索可以用方向数组 [(1,0), (-1,0), (0,1), (0,-1)] 来简化代码。