leetcode hot 100 单词搜索
79. 单词搜索
已解答
中等
相关标签
相关企业
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
import copy
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
# o（mnkk）的就是遍历一遍找到开头，对所有开头左dfs
m = len(board)
n = len(board[0])
visted = copy.deepcopy(board)
self.ret = False
def dfs(x,y,count):
if count==len(word)-1 :
self.ret = True
return
tmp = False
count+=1
if x>=0 and x<m-1 and y>=0 and y<n and board[x+1][y]==word[count] and visted[x+1][y]==0:
visted[x+1][y]=1
tmp1 = dfs(x+1,y,count)
tmp = tmp or tmp1
visted[x+1][y]=0
if x>=1 and x<m and y>=0 and y<n and board[x-1][y]==word[count] and visted[x-1][y]==0:
visted[x-1][y]=1
tmp2 = dfs(x-1,y,count)
tmp = tmp or tmp2
visted[x-1][y]=0
if x>=0 and x<m and y>=0 and y<n-1 and board[x][y+1]==word[count] and visted[x][y+1]==0:
visted[x][y+1]=1
tmp3 = dfs(x,y+1,count)
tmp = tmp or tmp3
visted[x][y+1]=0
if x>=0 and x<m and y>=1 and y<n and board[x][y-1]==word[count] and visted[x][y-1]==0:
visted[x][y-1]=1
tmp4 = dfs(x,y-1,count)
tmp = tmp or tmp4
visted[x][y-1]=0
return tmp
for i in range(m):
for j in range(n):
visted[i][j]=0
for i in range(m):
for j in range(n):
if board[i][j]==word[0]:
visted[i][j]=1
dfs(i,j,0)
# return True
visted[i][j]=0
# count=0
# while self.queue!=[]:
# if count==len(word)-1 and self.queue!=[]:
# return True
# size = len(self.queue)
# count+=1
# for i in range(size):
# tmp = self.queue[0]
# del self.queue[0]
# x=tmp[0]
# y=tmp[1]
# if x>=0 and x<m-1 and y>=0 and y<n and board[x+1][y]==word[count] and visted[x+1][y]==0:
# self.queue.append([x+1,y])
# visted[x+1][y]=1
# if x>=1 and x<m and y>=0 and y<n and board[x-1][y]==word[count] and visted[x-1][y]==0:
# self.queue.append([x-1,y])
# visted[x-1][y]=1
# if x>=0 and x<m and y>=0 and y<n-1 and board[x][y+1]==word[count] and visted[x][y+1]==0:
# self.queue.append([x,y+1])
# visted[x][y+1]=1
# if x>=0 and x<m and y>=1 and y<n and board[x][y-1]==word[count] and visted[x][y-1]==0:
# self.queue.append([x,y-1])
# visted[x][y-1]=1
return self.ret
这里我们的结构是使用dfs回溯遍历，因为每次开始之后遍历完之后visted需要变回原样