我正在完成这个 Leetcode 问题:https://leetcode.com/problems/word-search/我随机选择使用 while 循环和堆栈迭代地实现 DFS,但是在回溯时我遇到了一些不便,如果我递归地解决问题通常不会发生这种情况,即我只能考虑实现一个列表( visited_index
) 以跟踪我访问过的索引,并在回溯时关闭弹出值以将 bool 矩阵 visited
设置回 False
。
from collections import defaultdict
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
starting_points = defaultdict(list)
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
starting_points[board[i][j]].append((i,j))
start = starting_points[word[0]]
visited = [[False] * n for _ in range(m)]
stack = []
directions = [(1,0), (0,-1), (-1,0), (0,1)]
for s in start:
stack.append((s[0], s[1], 0))
visited_index = [] # EXTRA LIST USED
while stack:
x, y, count = stack.pop()
while len(visited_index) > count:
i, j = visited_index.pop()
visited[i][j] = False # SETTING BACK TO FALSE WHEN BACKTRACKING
if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or board[x][y] != word[count]:
continue
else:
visited[x][y] = True
visited_index.append((x,y))
if count + 1 == len(word):
return True
for d in directions:
i, j = x + d[0], y + d[1]
stack.append((i,j, count + 1))
else:
stack.clear()
for i in range(m):
for j in range(n):
visited[i][j] = False
return False
我相信在递归方法中,我可以在函数末尾将 visited
bool 值重置回 False
,而无需使用额外的列表.在使用堆栈进行迭代 DFS 时,有人建议不要引入额外的数据结构吗?
最佳答案
只要有子节点正在处理,我就会将父节点保留在堆栈中。然后,当所有子项都已处理并且您将父项从堆栈中弹出时,您将有适当的时间也删除该父项的已访问标记。
实现该想法的一种方法是在您放入堆栈的元组中添加一个信息:最后一个方向。您可以使用该信息来寻找下一个方向,如果有可用的有效方向,则将当前节点推回具有新方向的堆栈,然后将相应的子节点插入堆栈。后者为该“先前”方向指示获取一些默认值。例如-1。
我重新编写了您的代码以符合该想法:
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
stack = []
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
# 4th member of tuple is previous direction taken. -1 is none.
stack.append((i, j, 1, -1)) # count=1, side=-1
visited = [[False] * n for _ in range(m)]
directions = [(1,0), (0,-1), (-1,0), (0,1)]
while stack:
x, y, count, side = stack.pop()
# perform the success-check here, so it also works for 1-letter words.
if count == len(word):
return True
visited[x][y] = True # will already be True when side > -1
# find next valid direction
found = False
while side < 3 and not found:
side += 1
dx, dy = directions[side]
i, j = x + dx, y + dy
found = 0 <= i < m and 0 <= j < n and not visited[i][j] and board[i][j] == word[count]
if not found: # all directions processed => backtrack
visited[x][y] = False
continue
stack.append((x, y, count, side)) # put node back on stack
stack.append((i, j, count + 1, -1))
return False
关于python - 使用通过堆栈实现的迭代 DFS 时如何回溯,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64136564/