LeetCode0079.WordSearch【Medium】【Python】【DFS】ProblemLeetCode给定一个二维板和一个单词，判断该单词是否存在于网格中。单词可以由顺序的字母构成相邻单元格，其中“相邻”单元格是水平或垂直相邻的单元格。同一字母单元格不得使用多次。示例：棋盘=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]给定词=“ABCCED”，返回真。给定词=“SEE”，返回真。给定词=“ABCB”，返回假。问题给定一个二维网格和一个单词，找出网格中是否存在该单词。单词必须按字母顺序排列，通过相邻单元格中的字母，其中“相邻”单元格是水平或垂直相邻的单元格。同一单元格中的字母不允许重复使用。示例：board=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]给定单词="ABCCED"，返回true。给定word="SEE"，返回true。给定word="ABCB"，返回false。ideaDFSDFS四个方向搜索，访问Overdone用'#'标示，表示不可重复访问。记得参观结束再继续，因为还有其他路径。Python3代码类解决方案：defexist(self,board:List[List[str]],word:str)->bool:ifnotboard:returnFalseforiinrange(len(board)):forjinrange(len(board[0])):ifself.dfs(board,i,j,word):返回True返回Falsedefdfs(self,board,i,j,word):iflen(word)==0:如果i<0或i>=len(board)或j<0或j>=len(board[0])或word[0]!=board[i][j]则返回True：返回Falsetmp，board[i][j]=board[i][j],'#'#'#':已访问ans=self.dfs(board,i-1,j,word[1:])或self.dfs(board,i+1,j,word[1:])或self.dfs(board,i,j-1,word[1:])或self.dfs(board,i,j+1,word[1:])board[i][j]=tmp#recoverboard[i][j]returnans代码地址GitHub链接
