79. 单词搜索

题目链接：79. 单词搜索

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

核心思考：网格回溯（DFS）

这是一个典型的约束路径搜索问题，适用于深度优先搜索（DFS）加回溯。

1. 枚举起点：单词可能从矩阵中的任何一个格子开始。因此，我们需要双重循环遍历整个 board，将每一个格子作为 DFS 的起始点。
2. 状态递归：dfs(i, j, k) 代表当前正站在坐标 (i, j) 上，尝试匹配单词 word 的第 k 个字符。
   • 基础匹配：如果 board[i][j] 不等于 word[k]，匹配失败，折返。
   • 成功匹配：如果 k 已达到单词末尾且字符匹配，说明找到完整路径，返回 True。
3. 路径标记与回溯：
   • 题目规定同一个单元格不允许重复使用。因此，在进入下一层递归前，我们需要将当前格子加入 visited 集合（或在原数组上临时修改字符）。
   • 探测完该格子的上下左右四个邻居后，如果都未能找到完整单词，则需撤销操作，将当前格子从 visited 中移除（回溯），以便其他分支能再次使用。
4. 剪枝：一旦某个分支返回了 True，立即通过递归链条向上回传结果，停止其他所有方向的探索。

解题思路 (Python)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = set()
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(i, j, k):
            # 字符不匹配，直接返回
            if board[i][j] != word[k]:
                return False
            
            # 最后一个字符匹配成功，意味着找到路径
            if k == len(word) - 1:
                return True

            # 标记当前位置已访问
            visited.add((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 and (new_i, new_j) not in visited:
                    if dfs(new_i, new_j, k + 1):
                        return True

            # 回溯：撤销访问标记
            visited.remove((i, j))
            return False
        
        # 遍历矩阵寻找潜在起点
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True

        return False

复杂度分析

• 时间复杂度：$O(M \times N \times 3^L)$，其中 $M, N$ 为网格长宽，$L$ 为单词长度。我们需要枚举 $M \times N$ 个起点；在每一层递归中，除了进入的方向，有 3 个新方向可供开拓，路径深度为 $L$。
• 空间复杂度：$O(L)$。主要为递归栈的深度，以及 visited 集合在递归路径上占据的空间最大为 $L$。
  注意：尽管在代码中使用了 visited 集合增加了一些常数开销，但逻辑更加通用且不会改动原始数据。