使用trie的leetcode 212 word search II bug

Question

问题：给定一个m x n的字符板和一个字符串单词列表，返回板上的所有单词。

class Solution(object):
    def findWords(self, board, words):
        WORD_KEY = '$'
        trie = {}
        for word in words:
            node = trie
            for letter in word:
                # retrieve the next node; If not found, create a empty node.
                node = node.setdefault(letter, {})
            # mark the existence of a word in trie node
            node[WORD_KEY] = word
        
        rowNum = len(board)
        colNum = len(board[0])
        
        matchedWords = []
        
        def helper(row,col,trie):
            if trie.keys()[0]==WORD_KEY:
                matchedWords.append(trie[WORD_KEY])
                return
            if row>len(board)-1 or row<0 or col>len(board[0])-1 or col<0:
                return
            if board[row][col] == '*':
                return
            if board[row][col] in trie:
                for (rowOffset, colOffset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                    temp=board[row][col]
                    board[row][col]='*'
                    helper(row+rowOffset,col+colOffset,trie[temp])
                    board[row][col]=temp
            else:
                return
         
        for i in range(len(board)):
            for j in range(len(board[0])):
                helper(i,j,trie) 
        return matchedWords             

递归一直是我最大的问题，很难找到错误，我想知道我是如何在代码中出错的。错误的输出如下:[“誓言”，“誓言”，“誓言”，“誓言”，“吃”，“吃”，“吃”，“吃”，“吃”]，每个重复4次

而不仅仅是[宣誓，吃饭]

Answer 1

这是一个有效的方法--它纠正了helper函数中的一些问题：

def backtracking(row, col, parent):    
    letter = board[row][col]
    currNode = parent[letter]
            
    word_match = currNode.pop(WORD_KEY, False)
    if word_match:
       matchedWords.append(word_match)
            
       board[row][col] = '#'   # marked as visited already
            
       # Explore the neighbors in 4 directions
       for (rowOffset, colOffset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            newRow, newCol = row + rowOffset, col + colOffset     
            if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
                 continue
            if not board[newRow][newCol] in currNode:
                 continue
            backtracking(newRow, newCol, currNode)
        
        board[row][col] = letter   # end of Exploration, restore it
        
        #remove the matched leaf node in Trie.
        if not currNode:  parent.pop(letter)

    for row in range(rowNum):
        for col in range(colNum):
            if board[row][col] in trie:
                backtracking(row, col, trie)
        
    return matchedWords