LeetCode 79. 单词搜索 | Python

提示：

• board 和 word 中只包含大写和小写英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

思路：深度优化搜索、回溯

首先看题意，题目中要求单词必须按照字母顺序，在给定的二维数组中，找到单词。可通过相邻单元格的字母组成，这里【相邻】包括横向和纵向相邻的单元格，这里就涉及到一个偏移量的问题，但是同一个单元的字母不能够重复使用。

先看下如何去实现搜索？首先我们要先要对二维数组进行遍历，要先找到跟单词首字母相同的元素，这里要注意，当找到这个元素时，要先进行标记，因为题意要求字母不能重复使用。

当找到这个元素时，从当前元素的位置开始进行搜索，需要往四个方位进行搜索，看看相邻的单元格元素是否是单词的下一个字母，这里分为两种情况：

• 能够匹配时，从这个元素继续进行搜索
• 不能匹配时，返回 False，这里要进行回溯

当所有的字母完全匹配时，则返回 True。

具体的实现代码如下。

class Solution:
    directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]

    def exist(self, board: List[List[str]], word: str) -> bool:
 if len(board) == 0:
     return False
 
 # 四个方位偏移量
 

 rows = len(board)
 cols = len(board[0])

 # 这里用以标记元素是否使用
 # False 表示未使用
 # True 表示已使用
 marked = [[False for _ in range(cols)] for _ in range(rows)]

 # 先遍历，
 for row in range(rows):
     for col in range(cols):
      # 当找到所有元素时返回 True
      if self._search(row, col, board, word, 0, marked):
   return True
 return False

    def _search(self, i, j, board, word, index, marked):
 # 终止条件
 if index == len(word) - 1:
     return board[i][j] == word[index]

 # 只有匹配了才继续搜索
 if board[i][j] == word[index]:
     # 这里先标记元素，如果搜索不成功的情况下，解除标记
     marked[i][j] = True
     # 四个方位搜索
     for dx, dy in self.directions:
  nrow = i + dx
  ncol = j + dy

  # 限定边界，
  # 搜索时找相邻未使用过的元素
  if 0 <= nrow < len(board) and 0 <= ncol < len(board[0]) and not marked[nrow][ncol] and self._search(nrow, ncol, board, word, index + 1, marked):
      return True
     # 释放标记
     marked[i][j] = False
 return False