LeetCode 第 79 题：单词搜索

题目描述

给定一个二维字符网格 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

解题思路：回溯算法（深度优先搜索）

这个问题非常适合使用回溯算法（Backtracking）来解决。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是解（或者至少不是最后一个解），回溯算法会丢弃该解，并在上一步进行一些变化后再次尝试。

我们可以将搜索过程看作在一棵决策树上进行深度优先遍历（DFS）：

1. 起点：我们需要遍历网格中的每一个单元格，将其作为搜索的起点。
2. 决策：从当前单元格出发，我们有四个方向（上、下、左、右）可以探索下一个字符。
3. 约束条件：
   • 不能超出网格的边界。
   • 下一个单元格的字符必须等于单词 word 中下一个位置的字符。
   • 已经使用过的单元格不能再次使用（避免路径绕圈）。
4. 目标：匹配到单词 word 的最后一个字符，即成功。
5. 回溯：如果从当前单元格出发的某个路径无法匹配成功，我们需要“撤销”当前的选择（比如，将当前单元格标记为未访问），然后尝试另一个方向。

循序渐进解题过程

步骤 1：定义递归函数（回溯函数）

我们需要一个递归函数，它的核心职责是判断：从网格 board 的 (i, j) 位置开始，能否搜索到单词 word 从第 index 个字符开始的后缀。

函数签名可以设计为：
dfs(board, word, i, j, index) -> bool

• i, j：当前在网格中的坐标。
• index：当前需要匹配的字符在 word 中的索引。

步骤 2：递归终止条件

在递归函数中，我们首先要判断什么时候应该停止递归。

1. 成功条件：如果 index 已经等于单词 word 的长度，说明我们已经成功匹配了整个单词，返回 true。
2. 失败条件：
   • 当前坐标 (i, j) 超出了网格的边界。
   • 当前网格字符 board[i][j] 不等于单词中对应位置的字符 word[index]。
   • 当前单元格已经被访问过（已经在当前搜索路径中）。

如果满足任何失败条件，本次搜索失败，返回 false。

步骤 3：标记已访问状态

在进入当前单元格的搜索后，为了避免路径中重复使用同一个单元格，我们需要临时标记当前单元格为“已访问”。一个常见的技巧是修改网格本身的值，例如，将 board[i][j] 修改为一个特殊字符（如 ‘#’），表示此位置已使用。

步骤 4：探索四个方向

在当前单元格匹配成功并被标记后，我们开始向四个方向（上、下、左、右）进行深度优先搜索，尝试匹配下一个字符 word[index+1]。

只要任意一个方向的搜索返回了 true，就说明我们找到了一条完整的路径，整个搜索就是成功的。

步骤 5：回溯（恢复状态）

在尝试完四个方向后，无论成功与否，在返回结果之前，我们必须进行回溯操作。即撤销步骤 3 中的标记，将 board[i][j] 恢复为原来的字符。

这一步至关重要！因为当前路径的搜索已经结束，我们需要让其他可能的搜索路径（比如以另一个单元格为起点的路径）能够正常使用这个单元格。

步骤 6：主函数逻辑

在主函数中，我们遍历网格 board 的每一个单元格 (i, j)，将其作为搜索的起点，调用 dfs 函数。

• 只要有一次调用返回 true，说明找到了单词，立即返回 true。
• 如果遍历完所有起点都没有成功，则返回 false。

详细代码示例（Python）

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 获取网格的行数和列数
        rows, cols = len(board), len(board[0])
        
        # 定义回溯函数（深度优先搜索）
        def dfs(i, j, index):
            # 步骤 2：判断终止条件
            # 如果索引超出单词长度，说明匹配完成
            if index == len(word):
                return True
            # 如果越界或者当前字符不匹配，返回失败
            if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != word[index]:
                return False
            
            # 步骤 3：标记已访问状态
            # 临时将当前单元格内容保存，并标记为‘#’（表示已访问）
            temp = board[i][j]
            board[i][j] = '#'
            
            # 步骤 4：探索四个方向（上，下，左，右）
            # 检查四个方向是否有任意一个能找到后续的路径
            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))    # 左
            
            # 步骤 5：回溯，恢复状态
            # 将当前单元格恢复为原来的字符
            board[i][j] = temp
            
            return found
        
        # 步骤 6：主函数逻辑，遍历每个起点
        for i in range(rows):
            for j in range(cols):
                # 以 (i, j) 为起点，从单词的第0个字符开始搜索
                if dfs(i, j, 0):
                    return True
        return False

复杂度分析

• 时间复杂度：最坏情况下，我们需要遍历整个网格（M * N 个起点），并对每个起点进行深度优先搜索。DFS 的深度最多为单词长度 L，每个节点有 4 个分支（但受已访问标记限制，实际约为 3 个）。因此，最坏时间复杂度为 O(M * N * 4^L)。
• 空间复杂度：主要取决于递归调用栈的深度，即单词的长度 L。因此，空间复杂度为 O(L)。