79单词搜索[Python常见问题]

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"))

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 79单词搜索