Hard Trie + Backtrack Tries
In plain English: Given a grid of letters and a list of words, find which words can be spelled by tracing a path through adjacent cells.
Build a trie from the word list, then DFS from every cell. The trie prunes dead-end paths early — if the current prefix isn't in the trie, stop. Remove found words from the trie to avoid duplicates.
Prompt
Given an m x n board of characters and a list of words, return all words that can be formed by sequentially adjacent cells (horizontal or vertical). Each cell may only be used once per word.
Try to write it from scratch before scrolling down.
Solution
def find_words(board, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node['#'] = w # mark end with the word itself
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
ch = board[i][j]
if ch not in node:
return
nxt = node[ch]
if '#' in nxt:
result.append(nxt.pop('#')) # found word, remove to dedup
board[i][j] = '.' # mark visited
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 and board[ni][nj] != '.':
dfs(ni, nj, nxt)
board[i][j] = ch # restore
if not nxt: # prune empty trie branches
del node[ch]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
# Test: board = [["o","a","a","n"],["e","t","a","e"],
# ["i","h","k","r"],["i","f","l","v"]]
# find_words(board, ["oath","pea","eat","rain"]) == ["oath","eat"]