79. 单词搜索

思路
每次以当前位置为初始位置开始遍历，看是否找到单词
（以官方题解做出）
v:代表等于work[k]且已走过的位置

d:四个方向

回溯（遍历）：

匹配不上：终止

找到了：终止（先判断匹配再判断找到）

未终止，继续循环：记录当前已走过位置（等于work[k]），以当前位置向四周遍历，找到则往对应方向继续循环；四个方向都找不到匹配，则回退再继续遍历

class Solution(object):def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool""""""回溯三部曲：满足结果、匹配不上、继续搜索"""#方向d=[(0,1),(0,-1),(1,0),(-1,0)]#已经走过的位置v = set()def backtrack(i,j,k):#匹配不上if board[i][j]!=word[k]:return False#满足结果if k==len(word)-1:return True#当前字符满足，继续往下搜 ,先标记已经走过的位置   走过的位置不能再走v.add((i,j))r = False#当前位置往四个方向继续搜索for s1,s2 in d:s,t=s1+i,s2+jif (s>=0 and s<len(board)) and (t>=0 and t<len(board[0])) and (s,t) not in v:if backtrack(s,t,k+1):return True#四个方向都找不到，回退v.remove((i,j))for i in range(len(board)):for j in range(len(board[0])):#每次以当前位置为起点开始遍历，查看是否找到if backtrack(i,j,0):return Truereturn False

超限（更容易理解）：

class Solution(object):def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool""""""回溯三部曲：满足结果、匹配不上、继续搜索"""#方向# d=[(0,1),(0,-1),(1,0),(-1,0)]def backtrack(i,j,k):#满足结果if board[i][j]==word[k] and k==len(word)-1:return True#匹配不上if board[i][j]!=word[k]:return False#当前字符满足，继续往下搜#先标记已经走过的位置   走过的位置不能再走temp=board[i][j]board[i][j]=1#超限# for s1,s2 in d:#     s,t=s1+i,s2+j#     if (s>=0 and s<len(board)) and (t>=0 and t<len(board[0])) and backtrack(s,t,k+1):#         return Trueif i-1>=0 and k+1<len(word) and backtrack(i-1,j,k+1):return Trueif j-1>=0 and k+1<len(word) and backtrack(i,j-1,k+1):return Trueif i+1<len(board) and k+1<len(word) and backtrack(i+1,j,k+1):return Trueif j+1<len(board[0]) and k+1<len(word) and backtrack(i,j+1,k+1):return True#四个方向都找不到，还原board[i][j]=tempfor i in range(len(board)):for j in range(len(board[0])):#每次以当前位置为起点开始遍历，查看是否找到if backtrack(i,j,0):return Truereturn False