【LeetCode】79.单词搜索

**单词搜索**
================**题目描述**
-------------

给定一个二维字符网格和一个单词，找出该单词是否存在于网格中。

**示例1:**

输入:
[
 ['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']
]
'ABCCED'

输出:
True

输入:
[
 ['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']
]
'SCEA'

输出:
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.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

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