LeetCode 第 79 题：单词搜索

题目描述

给定一个 m x n 的二维字符网格 board 和一个字符串单词 word。你需要判断 word 是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格（相邻指水平或垂直相邻的单元格）内的字母构成。同一个单元格内的字母不允许被重复使用。

示例 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

解题思路详解

第一步：理解问题核心

这个问题要求我们在一个二维网格中寻找一个字符串，寻找路径必须是连续的（上下左右四个方向），且每个单元格只能使用一次。这本质上是一个图上的深度优先搜索（DFS）问题，需要配合回溯法来避免重复使用单元格。

第二步：确定搜索起点

由于单词可能从网格的任意位置开始匹配，我们需要遍历网格中的每个单元格，将其作为搜索的起点：

• 对每个单元格 (i, j)，检查它是否等于单词的第一个字符。
• 如果相等，从这个位置开始进行DFS搜索。

第三步：设计DFS递归函数

DFS函数需要以下参数：

1. 当前坐标 (i, j)
2. 当前匹配到单词的索引 index（表示已成功匹配了前index个字符）
3. 访问标记数组 visited（记录哪些单元格已被使用）

递归终止条件：

• 如果 index == word.length()，说明已匹配整个单词，返回true。
• 如果当前坐标越界，返回false。
• 如果当前单元格已被访问过，返回false。
• 如果当前单元格字符不等于 word[index]，返回false。

递归过程：

1. 标记当前单元格为已访问。
2. 向四个方向（上、下、左、右）进行DFS搜索。
3. 如果任意方向返回true，说明找到单词，返回true。
4. 否则，回溯：取消当前单元格的访问标记，返回false。

第四步：具体实现细节

def exist(board, word):
    if not board or not board[0] 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] = '#'  # 标记为已访问
        
        # 四个方向搜索
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右、左、下、上
        for dx, dy in directions:
            if dfs(i + dx, j + dy, index + 1):
                return True
        
        # 回溯：恢复单元格原始值
        board[i][j] = temp
        return False
    
    # 遍历每个起点
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True
    
    return False

第五步：复杂度分析

• 时间复杂度：O(m × n × 4^L)，其中m、n是网格尺寸，L是单词长度。最坏情况下需要遍历每个起点，每个起点最多有4^L种搜索路径。
• 空间复杂度：O(L)，主要取决于递归调用栈的深度，最大为单词长度L。

第六步：优化思路

1. 提前终止：如果单词长度大于网格单元格总数，直接返回false。
2. 反向搜索：如果单词末尾字符在网格中出现次数少于开头字符，可以反向搜索单词。
3. 剪枝优化：在DFS前检查剩余字符是否在网格中存在足够数量。

这个算法通过DFS+回溯系统地探索所有可能的路径，确保不重复使用单元格，是解决这类二维网格搜索问题的经典方法。