劍指 Offer 12. 矩陣中的路徑

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

嗯就是一個(gè)dfs,然后剪枝

class?Solution:

????def?exist(self,?board:?List[List[str]],?word:?str)?->?bool:

????????def?dfs(i,j,k):

????????????if?not?0<=i<len(board)?or?not?0<=j<len(board[0])?or?not?board[i][j]==word[k]:return?False

????????????if?k==len(word)-1:return?True

????????????board[i][j]=''

????????????res=dfs(i+1,j,k+1)or?dfs(i-1,j,k+1)or?dfs(i,j+1,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