79_单词搜索

类型：数组

• 79. 单词搜索 💛

  https://leetcode-cn.com/problems/word-search/

  ❓ 给定一个 m x n 的二维字符网格 board 和一个字符串单词 word，如果 word 存在于网格中，返回 true，否则返回 false。word 必须由 board 中的相邻格子（上下左右）按序构成。

  💡 DFS

  对每一个位置 (i, j) 都调用函数 check 进行检查，只有有一处返回 true，就说明网格中能够找到相应单词。为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。

  class Solution:
      def exist(self, board: List[List[str]], word: str) -> bool:
          directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
  
          def check(i: int, j: int, k: int) -> bool:
              if board[i][j] != word[k]:
                  return False
              if k == len(word) - 1:
                  return True
  
              visited.add((i, j))
              result = False
              for di, dj in directions:
                  newi, newj = i + di, j + dj
                  if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
                      if (newi, newj) not in visited:
                          if check(newi, newj, k + 1):
                              result = True
                              break
  
              visited.remove((i, j))
              return result
  
          h, w = len(board), len(board[0])
          visited = set()
          for i in range(h):
              for j in range(w):
                  if check(i, j, 0):
                      return True
  
          return False