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，否则回溯。

掌握回溯算法的使用方法，对于解决类似的问题非常重要。