Problem. Given a board of letters and a list of words, return all words that can be formed on the board using horizontal or vertical adjacency without reusing a cell.
This is the classic multiword trie backtracking pattern.
Examples:
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],words = ["oath","pea","eat","rain"]→["oath","eat"]in any orderboard = [["a","b"],["c","d"]],words = ["abcb"]→[]board = [["a"]],words = ["a","b"]→["a"]
Solution. Build a trie of all candidate words so every DFS path can stop immediately when its current prefix is impossible. Whenever you land on a trie node that marks a full word, record it and continue searching for longer matches.
class TrieNode(dict):
def __init__(self):
super().__init__()
self.word = None
def find_words(board, words):
root = TrieNode()
for word in words:
node = root
for char in word:
node = node.setdefault(char, TrieNode())
node.word = word
rows = len(board)
cols = len(board[0])
found = []
def dfs(row, col, node):
char = board[row][col]
if char not in node:
return
next_node = node[char]
if next_node.word is not None:
found.append(next_node.word)
next_node.word = None
board[row][col] = '#'
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr = row + dr
nc = col + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, next_node)
board[row][col] = char
for row in range(rows):
for col in range(cols):
dfs(row, col, root)
return found
O(m * n * 4^L) worst-case search, but the trie prunes heavily in practice; O(total word characters) trie space.
Gotchas.
- Without the trie, searching every word separately repeats the same prefix work many times.
- Clearing
next_node.wordafter finding it avoids duplicate outputs from different paths reaching the same stored word. - As in the single-word version, restore the board cell after each DFS path.