LeetCode 79. Word Search 题解

LeetCode 79. Word Search 题解题目描述给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 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思路使用深度优先搜索来遍历网格中的每个单元格对于每个单元格检查是否与单词的当前字符匹配如果匹配标记该单元格为已访问然后递归搜索其上下左右四个相邻的单元格如果递归到单词的末尾返回 true如果所有路径都搜索完毕仍未找到返回 false复杂度分析时间复杂度O(m × n × 4^L)其中 m 和 n 是网格的行数和列数L 是单词的长度。每个单元格最多被访问一次每次有 4 个方向可以选择。空间复杂度O(L)其中 L 是单词的长度。递归调用的栈空间取决于单词的长度。代码实现方法深度优先搜索class Solution: def exist(self, board: List[List[str]], word: str) - bool: m len(board) n len(board[0]) L len(word) # 定义方向上、右、下、左 directions [(-1, 0), (0, 1), (1, 0), (0, -1)] def dfs(i, j, k): # 如果已经匹配到单词的末尾返回 true if k L: return True # 检查边界条件和当前字符是否匹配 if i 0 or i m or j 0 or j n or board[i][j] ! word[k]: return False # 标记当前单元格为已访问 temp board[i][j] board[i][j] # # 搜索四个相邻的单元格 for dx, dy in directions: if dfs(i dx, j dy, k 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测试用例测试用例 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测试用例 4输入board [[a]], word a输出true总结本题是深度优先搜索的经典应用问题主要考察对 DFS 算法的理解和使用。通过使用 DFS我们可以遍历网格中的每个单元格尝试匹配单词的每个字符。DFS 的核心思想是从网格中的每个单元格开始递归地搜索其相邻的单元格检查是否能够匹配单词的所有字符。在搜索过程中需要标记已访问的单元格避免重复使用。这种方法不仅适用于单词搜索问题还可以应用于许多其他需要遍历二维网格的问题例如岛屿数量、最大面积岛屿等。掌握 DFS 的使用对于解决这类问题非常重要。