如何在使用基于栈的迭代DFS时进行回溯

Question

我在解决这道Leetcode问题： https://leetcode.com/problems/word-search/ 时，随意选择了使用while循环和堆栈来迭代地实现DFS，但是当回溯时遇到了一些不便，如果我是用递归方式做这个问题，通常不会出现这种情况，即我只能考虑实现一个列表 (visited_index) 来跟踪我已经访问的索引，并弹出值以将布尔矩阵 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 布尔值重置为 False，而无需使用额外的列表。 有没有人有什么建议，在使用堆栈进行迭代深度优先搜索时不引入额外的数据结构？

- alee18

---

哈哈，我正在做完全相同的LeetCode问题，遇到了完全相同的问题。感谢您提供答案。 - Tobiah Rex

Answer 1

在处理子节点时，我会将父节点保留在堆栈中。然后，在所有子节点都被处理完毕并从堆栈中弹出父节点时，您将有机会同时删除该父节点的已访问标记。

实现这个想法的一种方法是在放入堆栈的元组中再加入一个信息：上次采取的方向。您可以使用该信息查找下一个要采取的方向，如果有有效的方向可用，则将当前节点与新方向一起推回堆栈，然后将相应的子节点推入堆栈。后者会得到一个默认值作为“前一个”方向指示。例如-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

- trincot