How to backtrack when using a iterative DFS implemented via a stack

Question

I was completing this Leetcode problem: https://leetcode.com/problems/word-search/ and I randomly chose to implement the DFS iteratively with a while loop and a stack but I encountered some inconveniences when backtracking that I wouldn't normally occur if I had done the problem recursively i.e. I could only think of implementing a list (visited_index) to keep track of the indexes I had visited and pop values off to set the boolean matrix visited back to False when backtracking.

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

I believe that in a recursive approach I could have reset the the visited boolean value back to False at the end of the function without the need to use an extra list. Does anyone have any suggestions to not introduce an extra data structure when doing an iterative DFS with a stack?

Answer 1

I would keep the parent node on the stack for as long there are children being processed. Then when all children have been processed and you pop the parent from the stack you'll have the right moment to also remove the visited mark for that parent.

One way to implement that idea is to put one more information in the tuple that you put on the stack: the last direction that was taken. You can use that info to look for the next direction to take, and if there is a valid direction available, push the current node back on the stack with that new direction, and then push the corresponding child on the stack. The latter gets some default value for that "previous" direction indication. For example -1.

I reworked your code to align with that idea:

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