超级管理员

70686

帖子

13

回复

228

积分

楼主
发表于 2020-09-16 17:40:01 | 查看: 12 | 回复: 0
from typing import List
# 这个是广搜的思路。通过一个点向上下左右走,寻找board中word对应存在的单词。
# 直到找到word中最后一个单词。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# 定义二维数组的行和列。
col = len(board)
row = len(board[0])
# 定义广搜函数。
def dfs(index,x,y):
# 当寻找的单词个数够了之后,就返回正确
if index == len(word) - 1:
return True
# 因为题目要求不能够用重复的元素,所以这个先将这个数改掉。
temp = board[x][y]
board[x][y] = 0
# 深搜的精髓,上下左右寻找,判断哪个方向的节点符合。
for i,j in [[x + 1,y],[x - 1,y],[x,y + 1],[x,y -1]]:
# 判断节点的索引有没有出界。
if 0 <= i < col and 0 <= j < row and board[i][j] == word[index +1 ]:
if dfs(index + 1,i,j):
return True
# 还原。
board[x][y] = temp
return False
# 遍历二维数组,一个个进行判断。
for i in range(col):
for j in range(row):
if board[i][j] == word[0]:
if dfs(0, i, j):
return True
# 遍历完不符合的话就返回假。
else:
return False

A = Solution()
print(A.exist([
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],'ABCCED'))


本帖子中包含资源

您需要 登录 才可以下载,没有帐号?立即注册

您需要登录后才可以回帖 登录 | 立即注册

2018-2020 ©v2.1 冀ICP备19027484号

点击这里给我发消息