LeetCode 单词搜索题解

LeetCode 单词搜索题解题目描述给定一个 m x n 的二维字符网格 board 和一个字符串单词 word如果 word 存在于网格中返回 true否则返回 false。示例输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]],word ABCCED输出true解题思路方法回溯思路使用回溯算法来解决这个问题。遍历网格中的每个单元格作为起始位置。从起始位置开始尝试所有可能的选择如果当前字符等于单词的当前字符继续向四个方向搜索。如果越界或字符不匹配回溯。如果已经匹配到单词的最后一个字符返回 true。使用一个访问数组来记录已访问的单元格。复杂度分析时间复杂度O(m * n * 4^k)其中 m 和 n 是网格的行数和列数k 是单词的长度。空间复杂度O(m * n)用于存储访问数组。代码实现方法回溯# 单词搜索回溯 def exist(board, word): if not board or not board[0] or not word: return False m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] def backtrack(i, j, index): if index len(word): return True if i 0 or i m or j 0 or j n or visited[i][j] or board[i][j] ! word[index]: return False visited[i][j] True for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]: if backtrack(i di, j dj, index 1): visited[i][j] False return True visited[i][j] False return False for i in range(m): for j in range(n): if backtrack(i, j, 0): return True return False # 测试 def test_exist(): board [[A,B,C,E],[S,F,C,S],[A,D,E,E]] word ABCCED print(exist(board, word)) # 输出True board [[A,B,C,E],[S,F,C,S],[A,D,E,E]] word ABCB print(exist(board, word)) # 输出False if __name__ __main__: test_exist()测试用例测试用例 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 ABCB输出false总结单词搜索是一个经典的回溯算法问题它可以通过回溯算法来高效地解决。回溯算法的核心思想是从起始位置开始尝试所有可能的移动方向递归搜索如果找到目标单词则返回 true否则回溯。掌握回溯算法的使用方法对于解决类似的问题非常重要。