leetcode 212 word search II bugs using trie

Question

Problem: Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Here is my solution:

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

Recursion is always my biggest issue, and it is hard to find the mistake, I Want to know how I get it wrong with my code. The wrong output is such below: ["oath","oath","oath","oath","eat","eat","eat","eat"], each repeated 4 times

instead of just [oath,eat]

it is leetcode number 212, leetcode.com/problems/word-search-ii — bot99zjc
@bot99zjc add the problem description to the question, rather than adding a link to it — Abhinav Mathur
@bot99zjc your program has some problems - including last statement exposed a formatting issue. Please check my revised one in the Post. — Daniel Hao

Daniel Hao Daniel Hao · Accepted Answer · 2021-01-23T14:13:29

This is a working one - it has correct some issues in the helper function:

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

leetcode 212 word search II bugs using trie

1 Answers