79。词搜索主题来源：https://leetcode-cn.com/problems/word-search主题给定一个二维网格和一个词，找出该词是否存在于网格中。单词必须按字母顺序排列，通过相邻单元格中的字母，其中“相邻”单元格是水平或垂直相邻的单元格。同一单元格中的字母不允许重复使用。示例：board=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]给定word="ABCCED",返回true给定word="SEE",返回true给定word="ABCB",返回false提示：board和word只包含大小写英文字母。1<=board.length<=2001<=board[i].length<=2001<=word.length<=10^3解题思路：深度优化搜索，回溯先看意义问题，问题中的单词必须是Findthewordsinthegiven2Darray,alphabetically。它可以由相邻单元格的字母组成。这里[adjacent]包括水平和垂直相邻的单元格。这就涉及到偏移的问题，但是同一个cell的字母是不能重复使用的。我们先来看看如何实现搜索？首先，我们要先遍历二维数组，找到与单词首字母相同的元素。这里需要注意的是，找到这个元素的时候，一定要先标记出来，因为题意要求字母不能重复使用。当找到这个元素时，搜索从当前元素的位置开始。需要从四个方向搜索，看相邻的单元格元素是不是单词的下一个字母。这里有两种情况：能匹配到，从该元素查找不匹配时返回False，回溯到所有字母完全匹配时返回True。具体实现代码如下。代码实现类解：directions=[(1,0),(0,-1),(-1,0),(0,1)]defexist(self,board:List[List[str]],word:str)->bool:iflen(board)==0:returnFalse#四个方向偏移rows=len(board)cols=len(board[0])#这个用来标记元素是否被使用#False表示未使用#True表示marked=[[Falsefor_inrange(cols)]for_inrange(rows)]#先遍历，forrowinrange(rows):forcolinrange(cols):#ReturnTrue当找到所有元素时ifself._search(row,col,board,word,0,marked):returnTruereturnFalsedef_search(self,i,j,board,word,index,marked):#终止条件ifindex==len(word)-1:returnboard[i][j]==word[index]#只有匹配才继续搜索ifboard[i][j]==word[index]:#这里先标记元素，如果搜索不成功，取消标记marked[i][j]=True#四个方向搜索dx,dyinself.directions:nrow=i+dxncol=j+dy#限制边界,#搜索时查找相邻未使用的元素if0<=nrow
