LeetCode-79. 单词搜索

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

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

示例:

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

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

 1 class Solution:
 2     def exist(self, board: List[List[str]], word: str) -> bool:
 3         for i in range(len(board)):
 4             for j in range(len(board[0])):
 5                 if self.valied(board, i, j, word, 0):
 6                     return True
 7         return False
 8     
 9     def valied(self,board,i,j,word,wordIndex):
10         if wordIndex == len(word):
11             return True
12         if i<0 or i >=len(board) or j<0 or j>=len(board[0]) or word[wordIndex] != board[i][j]:
13             return False
14         board[i][j] = "#"   #之所以在此處要把儅前的數進行改變成  #  是因爲題目要求每一個 元素只能使用一次
15         
16         found = self.valied(board,i+1,j,word,wordIndex+1) or 
17                 self.valied(board,i,j+1,word,wordIndex+1) or 
18                 self.valied(board,i-1,j,word,wordIndex+1) or 
19                 self.valied(board,i,j-1,word,wordIndex+1)
20         board[i][j] = word[wordIndex]       #結束 DFS 之後需要把改變的數值再修改回來 以免影響下一次的DFS操作
21 
22         return found

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。