分析
其实就是个深度优先搜索。可以设置一个visit数组，标记已经走过的路段。注意判断dfs的退出条件。
写递归就是这样，先想好退出条件，再不断的缩小问题规模，就这样。
深度优先搜索法
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if len(board) == 0 or len(board[0]) == 0: return word == ''
x,y = len(board), len(board[0])
visited = [[False for i in range(y)] for j in range(x)]
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(visited, i, j, board, word):
return True
return False
def dfs(self, visited, x, y, board, word):
if not word: return True
target = word[0]
if target != board[x][y]: return False
if not word[1:]: return True
visited[x][y] = True
if x-1>=0 and not visited[x-1][y]:
flag = self.dfs(visited, x-1, y, board, word[1:])
if flag: return flag
if x+1 < len(board) and not visited[x+1][y]:
flag = self.dfs(visited, x+1, y, board, word[1:])
if flag: return flag
if y-1>=0 and not visited[x][y-1]:
flag = self.dfs(visited, x, y-1, board, word[1:])
if flag: return flag
if y+1<len(board[0]) and not visited[x][y+1]:
flag = self.dfs(visited, x, y+1, board, word[1:])
if flag: return flag
visited[x][y] = False
return False