【LeetCode】79.单词搜索
发布人:shili8
发布时间:2025-03-15 08:23
阅读次数:0
**单词搜索**
================**题目描述**
-------------
给定一个二维字符网格和一个单词,找出该单词是否存在于网格中。
**示例1:**
输入: [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 'ABCCED' 输出: True
**示例2:**
输入: [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 'SCEA' 输出: False
**解决方案**
------------### 方法一:深度优先搜索(DFS)
我们可以使用 DFS 来遍历网格中的每个单元格,并检查是否存在给定的单词。
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: if not board or not word: return False for i in range(len(board)): for j in range(len(board[0])): if self.dfs(board, i, j, word): return True return False def dfs(self, board, i, j, word): # 如果单词长度为1,且当前单元格的值与单词匹配,则返回 True if len(word) ==1 and board[i][j] == word: return True # 如果当前单元格的值不匹配或已经访问过,则返回 False if board[i][j] != word[0]: return False # 将当前单元格标记为已访问 temp, board[i][j] = board[i][j], '/' # 递归检查上下左右四个方向是否存在单词 res = self.dfs(board, i-1, j, word[1:]) or self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i, j-1, word[1:]) or self.dfs(board, i, j+1, word[1:]) # 恢复当前单元格的值 board[i][j] = temp return res
### 方法二:广度优先搜索(BFS)
我们可以使用 BFS 来遍历网格中的每个单元格,并检查是否存在给定的单词。
from collections import dequeclass Solution: def exist(self, board: List[List[str]], word: str) -> bool: if not board or not word: return False for i in range(len(board)): for j in range(len(board[0])): if self.bfs(board, i, j, word): return True return False def bfs(self, board, i, j, word): # 如果单词长度为1,且当前单元格的值与单词匹配,则返回 True if len(word) ==1 and board[i][j] == word: return True # 如果当前单元格的值不匹配或已经访问过,则返回 False if board[i][j] != word[0]: return False # 将当前单元格标记为已访问 temp, board[i][j] = board[i][j], '/' # 使用 BFS 遍历上下左右四个方向 queue = deque([(i, j)]) visited = {(i, j)} while queue: x, y = queue.popleft() if self.bfs_helper(board, x-1, y, word[1:]) or self.bfs_helper(board, x+1, y, word[1:]) or self.bfs_helper(board, x, y-1, word[1:]) or self.bfs_helper(board, x, y+1, word[1:]): return True for dx, dy in [(-1,0), (1,0), (0, -1), (0,1)]: nx, ny = x + dx, y + dy if0 <= nx < len(board) and0 <= ny < len(board[0]) and (nx, ny) not in visited: queue.append((nx, ny)) visited.add((nx, ny)) # 恢复当前单元格的值 board[i][j] = temp return False def bfs_helper(self, board, i, j, word): if len(word) ==1 and board[i][j] == word: return True if board[i][j] != word[0]: return False temp, board[i][j] = board[i][j], '/' queue = deque([(i, j)]) visited = {(i, j)} while queue: x, y = queue.popleft() if self.bfs_helper(board, x-1, y, word[1:]) or self.bfs_helper(board, x+1, y, word[1:]) or self.bfs_helper(board, x, y-1, word[1:]) or self.bfs_helper(board, x, y+1, word[1:]): return True for dx, dy in [(-1,0), (1,0), (0, -1), (0,1)]: nx, ny = x + dx, y + dy if0 <= nx < len(board) and0 <= ny < len(board[0]) and (nx, ny) not in visited: queue.append((nx, ny)) visited.add((nx, ny)) board[i][j] = temp return False
### 方法三:回溯法我们可以使用回溯法来遍历网格中的每个单元格,并检查是否存在给定的单词。
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: if not board or not word: return False for i in range(len(board)): for j in range(len(board[0])): if self.backtrack(board, i, j, word): return True return False def backtrack(self, board, i, j, word): # 如果单词长度为1,且当前单元格的值与单词匹配,则返回 True if len(word) ==1 and board[i][j] == word: return True # 如果当前单元格的值不匹配或已经访问过,则返回 False if board[i][j] != word[0]: return False # 将当前单元格标记为已访问 temp, board[i][j] = board[i][j], '/' # 递归检查上下左右四个方向是否存在单词 res = self.backtrack(board, i-1, j, word[1:]) or self.backtrack(board, i+1, j, word[1:]) or self.backtrack(board, i, j-1, word[1:]) or self.backtrack(board, i, j+1, word[1:]) # 恢复当前单元格的值 board[i][j] = temp return res
### 方法四:动态规划我们可以使用动态规划来遍历网格中的每个单元格,并检查是否存在给定的单词。
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: if not board or not word: return False for i in range(len(board)): for j in range(len(board[0])): if self.dp(board, i, j, word): return True return False def dp(self, board, i, j, word): # 如果单词长度为1,且当前单元格的值与单词匹配,则返回 True if len(word) ==1 and board[i][j] == word: return True # 如果当前单元格的值不匹配或已经访问过,则返回 False if board[i][j] != word[0]: return False # 将当前单元格标记为已访问 temp, board[i][j] = board[i][j], '/' # 使用动态规划遍历上下左右四个方向 dp_table = [[False for _ in range(len(board[0]))] for _ in range(len(board))] for k in range(1, len(word)): for x in range(len(board)): for y in range(len(board[0])): if board[x][y] == word[k]: dp_table[x][y] = self.dp_helper(dp_table, x-1, y, word[k+1:]) or self.dp_helper(dp_table, x+1, y, word[k+1:]) or self.dp_helper(dp_table