目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

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

二、解题思路

DFS+回溯，注意被使用过的元素需要进行标记。

三、代码

      class Solution:
      def exist(self, board: list, word: str) -> bool:
       m = len(board)
       n = len(board[0])
       l = len(word)
       mark = [[0 for _ in range(n)] for _ in range(m)]
      if m == 0 or n == 0:
      return False
      def dfs(index, x, y):
      # print(x, y)
      # print(board[x][y], index)
      if index == l:
      return True
      if x < 0 or x >= m or y < 0 or y >= n:
      return False
      if board[x][y] != word[index]:
      # print(board[x][y], word[index])
      return False
      # print(board[x][y], (x, y))
      if mark[x][y] == 0:
       mark[x][y] = 1
      else:
      return False
      for i in range(index, l):
      if dfs(i + 1, x + 1, y) or dfs(i + 1, x - 1, y) or dfs(i + 1, x, y + 1) or dfs(i + 1, x, y - 1):
      return True
       mark[x][y] = 0
      break
      return False
      for i in range(m):
      for j in range(n):
      if board[i][j] == word[0]:
      if dfs(0, i, j):
      return True
      return False
      if __name__ == '__main__':
       board = [["A","B","C","E"],
       ["S","F","C","S"],
       ["A","D","E","E"]]
       word = "ABCB" #""SEE" # "ABCCED"
       s = Solution()
       ans = s.exist(board, word)
       print(ans)
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108562065