行业网站建设的书,网站开发神书,青海省住房城乡建设厅网站,西安公司思路 每次以当前位置为初始位置开始遍历#xff0c;看是否找到单词 #xff08;以官方题解做出#xff09; v:代表等于work[k]且已走过的位置
d:四个方向
回溯#xff08;遍历#xff09;#xff1a;
匹配不上#xff1a;终止
找到了#xff1a;终止#xff08;先… 思路 每次以当前位置为初始位置开始遍历看是否找到单词 以官方题解做出 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 klen(word)-1:return True#当前字符满足继续往下搜 ,先标记已经走过的位置 走过的位置不能再走v.add((i,j))r False#当前位置往四个方向继续搜索for s1,s2 in d:s,ts1i,s2jif (s0 and slen(board)) and (t0 and tlen(board[0])) and (s,t) not in v:if backtrack(s,t,k1):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 klen(word)-1:return True#匹配不上if board[i][j]!word[k]:return False#当前字符满足继续往下搜#先标记已经走过的位置 走过的位置不能再走tempboard[i][j]board[i][j]1#超限# for s1,s2 in d:# s,ts1i,s2j# if (s0 and slen(board)) and (t0 and tlen(board[0])) and backtrack(s,t,k1):# return Trueif i-10 and k1len(word) and backtrack(i-1,j,k1):return Trueif j-10 and k1len(word) and backtrack(i,j-1,k1):return Trueif i1len(board) and k1len(word) and backtrack(i1,j,k1):return Trueif j1len(board[0]) and k1len(word) and backtrack(i,j1,k1):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
