LeetCode 第 79 题：单词搜索（Word Search）

我们来学习一个经典的回溯算法题目——“单词搜索”。

题目描述

给定一个 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

解题思路详解

这个问题的核心是：在一个二维网格中，从一个起点出发，向四个方向尝试行走，寻找一条路径，使得路径上的字符连起来正好是目标单词。由于路径可能分叉，并且需要避免走回头路，这非常适合用回溯算法（Backtracking）来解决。

回溯算法可以理解为一种试探性的搜索。我们尝试一条路径，如果走到某一步发现走不通（不符合条件），就退回到上一步，尝试其他的可能性。

具体步骤

1. 遍历起点：
   单词可能从网格中的任何一个格子开始。因此，我们首先要遍历整个网格，以每个格子作为搜索的起点。

2. 定义回溯函数：
   我们需要定义一个递归函数 backtrack(i, j, index)，其职责是判断：从网格的 (i, j) 位置出发，能否匹配到单词 word 中从第 index 个字符开始的后缀。

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

3. 回溯函数的终止条件：

   • 成功条件： 如果 index 的值等于单词 word 的长度，说明我们已经成功匹配了整个单词，返回 true。
   • 失败条件：
     • 坐标 (i, j) 超出了网格的边界。
     • 当前网格的字符 board[i][j] 不等于单词中第 index 个字符 word[index]。
     • 当前网格的字符已经被访问过（为了避免重复使用）。
       出现以上任何一种情况，都意味着当前路径失败，返回 false。

4. 回溯的核心过程（试探与回溯）：
   a. 标记已访问： 当进入 (i, j) 格子时，为了避免在后续的搜索中重复使用这个格子，我们需要将其标记为“已访问”。一个常见的技巧是修改网格的值，例如，将 board[i][j] 暂时改为一个特殊字符（如 '#'）。
   b. 探索四个方向： 向当前格子的上、下、左、右四个方向进行递归搜索，尝试匹配下一个字符 word[index+1]。只要有一个方向返回 true，就说明找到了一条可行路径。
   c. 恢复现场（回溯）： 在结束对当前格子的上下左右探索后，我们需要进行“回溯”操作。也就是将之前标记为已访问的格子恢复原状（将 '#' 改回原来的字母）。这一步至关重要，因为它保证了在尝试其他路径时，这个格子是可用的。

5. 主函数逻辑：
   遍历网格中的每一个格子 (i, j)，将其作为起点调用 backtrack(i, j, 0)（从单词的第一个字符开始匹配）。如果任何一个起点返回 true，整个函数就返回 true。如果所有起点都尝试失败，则返回 false。

让我们通过一个微型例子来模拟这个过程

假设网格为：
[['A', 'B']]
单词为：”AB”

1. 起点 (0,0)： 字符 'A' 匹配 word[0] ('A')。
   • 标记 (0,0) 为 '#'。网格变为 [['#', 'B']]。
   • 现在要匹配 word[1] ('B')。向四个方向探索：
     • 上、下：越界，忽略。
     • 左：越界，忽略。
     • 右：到达 (0,1)，字符 'B' 匹配 word[1] ('B')！成功！
     • 递归调用返回 true。
   • 回溯： 在返回前，恢复 (0,0) 的值为 'A'。网格变回 [['A', 'B']]。
2. 主函数收到 true，最终结果为 true。

如果单词是 “BA”，过程类似，只是起点需要从 (0,1) 开始。

复杂度分析

• 时间复杂度： 最坏情况下，我们需要遍历整个网格（m*n 个起点），对于每个起点，回溯过程在最坏情况下需要探索所有 4^L 条路径（L 是单词长度），但通过剪枝（遇到不匹配就返回），实际运行会好很多。最坏时间复杂度为 O(m * n * 4^L)。
• 空间复杂度： 主要是递归调用栈的深度，最大为单词长度 L，所以是 O(L)。

代码实现（Python）

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 右，左，下，上
        m, n = len(board), len(board[0])
        
        def backtrack(i, j, index):
            # 终止条件1：当前字符不匹配
            if board[i][j] != word[index]:
                return False
            # 终止条件2：已匹配完整个单词
            if index == len(word) - 1:
                return True
            
            # 保存当前格子的字符，并标记为已访问
            temp = board[i][j]
            board[i][j] = '#'
            
            # 向四个方向进行探索
            for dx, dy in directions:
                new_i, new_j = i + dx, j + dy
                # 检查新坐标是否在网格内
                if 0 <= new_i < m and 0 <= new_j < n:
                    if backtrack(new_i, new_j, index + 1):
                        return True
            
            # 回溯：恢复当前格子的状态
            board[i][j] = temp
            return False
        
        # 主循环：尝试每一个格子作为起点
        for i in range(m):
            for j in range(n):
                if backtrack(i, j, 0):
                    return True
        return False

总结

单词搜索是一个典型的回溯算法应用题，它清晰地展示了回溯算法的三板斧：

1. 选择： 选择当前格子的一个邻接方向进行探索。
2. 约束： 检查坐标是否合法、字符是否匹配、是否已访问。
3. 撤销： 在探索完所有可能性后，撤销当前的选择（恢复网格状态），以便进行下一次尝试。

理解了这个过程，你就能掌握解决此类二维网格搜索问题的核心技巧。