題目描述
給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。
單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。
例如，在下面的 3×4 的矩陣中包含單詞 “ABCCED”（單詞中的字母已標(biāo)出）。
示例 1：
輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
輸出：true
示例 2：
輸入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
輸出：false
思路分析
一道非常經(jīng)典的矩陣搜索題。
直接回溯。
1.確定循環(huán)體
肯定是要遍歷矩陣中的每一個(gè)格子，以每一個(gè)格子為起點(diǎn)向外搜索。
for i in range(len(board)):
for j in range(len(board[0])):
2.確定回溯體參數(shù)
顯然需要當(dāng)前遍歷的格子下標(biāo)i和j，還需要當(dāng)前遍歷的單詞下標(biāo)k。def dfs(i,j,k):
3.確定回溯體
在回溯的過(guò)程中，如果遇到邊界，則立即回退，遇到不符合單詞的字符，也立即回退。
if not 0<=i<len(board) or not 0<= j<len(board[0]) or board[i][j] != word[k]:
return False
當(dāng)前遍歷單詞的下標(biāo)k如果遍歷到最后了，說(shuō)明此時(shí)找到了完整的單詞：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-650124.html
if len(word)-1 == k:
return True
后面就是連續(xù)的三步，
1，首先將所有遍歷過(guò)的格子都弄成空，防止重復(fù)遍歷。
2. 回溯尋找當(dāng)前格子的四周。
3. 回退的時(shí)候?qū)⒆兛盏母褡幼兓卦瓉?lái)的數(shù)值。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-650124.html
board[i][j] = ' '
res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)
board[i][j] = word[k]
完整代碼
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# k為當(dāng)前word遍歷的下標(biāo)
def dfs(i,j,k):
if not 0<=i<len(board) or not 0<= j<len(board[0]) or board[i][j] != word[k]:
return False
if len(word)-1 == k:
return True
board[i][j] = ' '
res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)
board[i][j] = word[k]
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i,j,0):
return True
return False
到了這里，關(guān)于劍指 Offer 12. 矩陣中的路徑(回溯 DFS)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
