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+j
if (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 True
return 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 True
if i-1>=0 and k+1<len(word) and backtrack(i-1,j,k+1):
return True
if j-1>=0 and k+1<len(word) and backtrack(i,j-1,k+1):
return True
if i+1<len(board) and k+1<len(word) and backtrack(i+1,j,k+1):
return True
if j+1<len(board[0]) and k+1<len(word) and backtrack(i,j+1,k+1):
return True
#四个方向都找不到,还原
board[i][j]=temp
for i in range(len(board)):
for j in range(len(board[0])):
#每次以当前位置为起点开始遍历,查看是否找到
if backtrack(i,j,0):
return True
return False