目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

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

示例:

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