Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

## leetcode 79. 单词搜索 word search

sxwxs 2020-02-08 09:36:49 阅读数:18 评论数:0 点赞数:0 收藏数:0

https://leetcode-cn.com/probl...

### 解题思路

``[['A', 'B']], 'ABA' ``
``````[['A', 'B'],
['D', 'C']]
'ABCDA' ``````

``````[["A","B","C","E"],
["S","F","E","S"],
["A","D","E","E"]],
"ABCESEEEFS"``````
``````0 0 A
0 1 B
0 2 C
0 3 E
1 3 S
1 2 E
2 2 E
2 3 E
backtrack
backtrack
backtrack
2 3 E
2 2 E
1 2 E
1 1 F
1 0 S``````

### 代码

``````class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
n = len(board)
m = len(board[0])
def dfs(i, j, index):
mp[i][j] = False
#print('\t' * index, i, j, word[index-1])
if index == len(word):
return True
for ii, jj in [(0,1),(0,-1),(1,0),(-1,0)]:
if 0 <= i + ii < n and 0 <= j + jj < m and board[i+ii][j+jj] == word[index] and mp[i+ii][j+jj]:
if dfs(i+ii, j+jj, index + 1):
return True
#print('backtrack')
mp[i][j] = True
return False
for i in range(n):
for j in range(m):
if board[i][j] == word[0]:
mp = [[True] * m for i in range(n)]
if dfs(i, j, 1):
return True
return False``````

https://segmentfault.com/a/1190000021704847