<h3><a title="题目描述" href="https://leetcode-cn.com/problems/word-search/">题目描述</a></h3>
![file](https://i.loli.net/2020/09/13/u6KSrviTymxng9V.png)
<h4>方法一</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
directions = [(0,1),(0,-1),(1,0),(-1,0)]
def traceback(i,j,k):
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
visited.add((i,j))
res = False
for direct in directions:
new_i, new_j = i + direct[0], j + direct[1]
if 0 <= new_i < len(board) and 0 <= new_j < len(board[0]):
if ((new_i,new_j)) not in visited:
if traceback(new_i,new_j,k+1):
res = True
break
visited.remove((i,j))
return res
visited = set()
for i in range(len(board)):
for j in range(len(board[0])):
if traceback(i,j,0):
return True
return False
</pre>
<p> </p>
## 思路
- directions 存储方向
- visited记录访问节点
- 未采用的结果回溯 visited.remove()
Leetcode79 单词搜索