Word Search II

def findWords(board, words):
    trie = {}
    for word in words:
        node = trie
        for char in word:
            node = node.setdefault(char, {})
        node["$"] = word
    
    result = []
    visited = set()
    
    def dfs(i, j, node):
        if "$" in node:
            result.append(node["$"])
            del node["$"]
        
        for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < len(board) and 0 <= nj < len(board[0]):
                if (ni, nj) not in visited and board[ni][nj] in node:
                    visited.add((ni, nj))
                    dfs(ni, nj, node[board[ni][nj]])
                    visited.remove((ni, nj))
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] in trie:
                visited.add((i, j))
                dfs(i, j, trie[board[i][j]])
                visited.remove((i, j))
    
    return result