章节 38 | 面试题：二维网格中的单词搜索问题

在算法面试中，二维网格中的单词搜索问题是一个既考验逻辑思维又涉及深度优先搜索（DFS）或广度优先搜索（BFS）等算法技巧的经典问题。此类问题要求我们在给定的二维字符网格中，判断是否存在一条路径，该路径上的字符按顺序连接起来恰好构成给定的单词。解决此类问题，不仅能提升我们对网格搜索算法的理解，还能锻炼我们处理复杂数据结构和逻辑判断的能力。

38.1 问题描述

给定一个二维网格（二维字符数组）和一个单词，找到该单词在网格中的一条路径。路径可以从网格中的任意一格开始，每次可以移动到相邻的格子（上、下、左、右），并且路径上的字符按顺序连接起来要构成单词。网格中的字符可以重复使用。

38.2 示例

假设有以下网格和单词：

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

返回 true，因为存在一条路径“A -> B -> C -> C -> E -> D”，按顺序连接起来的字符正好是 “ABCCED”。

38.3 解题思路

1. 深度优先搜索（DFS）：

   • 从网格的每个位置开始尝试搜索。
   • 使用一个与网格相同大小的布尔数组来记录已经访问过的位置，避免重复访问。
   • 对于每个起始位置，递归地向四个方向（上、下、左、右）搜索，同时检查路径上的字符是否与单词匹配。
   • 如果在搜索过程中找到了完整的单词，则返回 true。
   • 如果搜索完所有可能的路径仍未找到匹配的单词，则返回 false。

2. 广度优先搜索（BFS）：

   • 虽然BFS不是解决此类问题的首选方法（因为它通常比DFS消耗更多内存），但在某些情况下（如需要找到最短路径时）可以考虑。
   • 使用队列来实现BFS，将每个待探索的位置和当前已匹配的单词部分作为状态存入队列。
   • 遍历队列，对于每个状态，检查其相邻位置，并更新状态和队列。
   • 当队列为空或找到匹配的单词时停止搜索。

38.4 深度优先搜索（DFS）实现

下面是一个使用DFS解决该问题的Python代码示例：

def exist(board, word):
    if not board or not board[0] or not word:
        return False
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]
    def dfs(r, c, index):
        # 边界条件或当前字符不匹配
        if r < 0 or r >= rows or c < 0 or c >= cols or visited[r][c] or board[r][c] != word[index]:
            return False
        # 所有字符都已匹配
        if index == len(word) - 1:
            return True
        visited[r][c] = True  # 标记为已访问
        # 递归地向四个方向搜索
        found = (dfs(r + 1, c, index + 1) or  # 下
                 dfs(r - 1, c, index + 1) or  # 上
                 dfs(r, c + 1, index + 1) or  # 右
                 dfs(r, c - 1, index + 1))    # 左
        visited[r][c] = False  # 回溯，撤销访问标记
        return found
    # 从每个格子开始搜索
    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True
    return False
# 示例用法
board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]
word = "ABCCED"
print(exist(board, word))  # 输出: True

38.5 优化与考虑

• 剪枝：在DFS过程中，如果当前位置已经不可能形成完整的单词（例如，剩余单词长度大于从当前位置可达的未访问格子数），可以提前终止搜索。
• 空间复杂度：DFS的空间复杂度主要由递归栈决定，对于最坏情况（即网格中的所有格子都需要被访问），空间复杂度接近网格大小。可以通过迭代（使用栈模拟递归）来优化空间使用，但这会牺牲一些代码的可读性。
• 特殊字符处理：如果网格中包含特殊字符（如’#’表示不可通行的格子），可以在DFS中增加相应的判断逻辑。
• 多解问题：题目通常只要求判断是否存在解，但如果需要找到所有解或最短路径，则需要对算法进行相应的调整。

38.6 结论

二维网格中的单词搜索问题是算法面试中常见的难题之一，它不仅考察了面试者对DFS/BFS等搜索算法的理解，还考验了面试者处理复杂逻辑和边界条件的能力。通过深入分析和实践，我们可以更好地掌握这类问题的解决方法，为未来的面试和技术挑战做好准备。