LeetCode 212 Word Search II - Implementation

Build trie, DFS from each cell following trie paths.

def findWords(board, words): trie = {} for word in words: node = trie for c in word: node = node.setdefault(c, {}) node['$'] = word

result = []
m, n = len(board), len(board[0])

def dfs(i, j, node):
    char = board[i][j]
    if char not in node:
        return
    nextNode = node[char]
    if '$' in nextNode:
        result.append(nextNode['$'])
        del nextNode['$']
    board[i][j] = '#'
    for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < m and 0 <= nj < n:
            dfs(ni, nj, nextNode)
    board[i][j] = char

for i in range(m):
    for j in range(n):
        dfs(i, j, trie)
return result

Time depends on board and trie structure. Space: $O(\sum |word|)$.