TL;DR
Build a trie of all the words, then one backtracking DFS per board cell walks the board and the trie in lockstep, with node pruning as words are found — O(m·n · 4 · 3^(L-1)) time for max word length L, O(total word characters) space.
Approach 1 — Brute force (Word Search I, once per word)
Run the classic single-word backtracking search independently for every word in the list.
class Solution:
def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
m, n = len(board), len(board[0])
def exists(word: str) -> bool:
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if not (0 <= r < m and 0 <= c < n):
return False
if board[r][c] != word[i]:
return False
board[r][c] = "#" # mark visited
found = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
board[r][c] = word[i] # unmark
return found
return any(
dfs(r, c, 0) for r in range(m) for c in range(n)
)
return [w for w in words if exists(w)]
One word costs O(m·n · 3^(L-1)) — every starting cell, then up to 3 fresh directions per step (you never go back the way you came). Multiply by 3·10^4 words and the worst case is roughly 3·10^4 · 144 · 3^9 ≈ 8·10^10 steps: the per-word repetition is exactly what the constraints are designed to kill.
Approach 2 — Trie + one shared backtracking DFS
The insight: a DFS path through the board spells a string one letter at a time, and a trie can tell you in O(1) whether any word in the whole list continues with the next letter. So instead of asking the board “does word w exist?” once per word, walk the board once while dragging a trie pointer along: the moment the trie has no child for a neighbor’s letter, every word sharing that prefix is eliminated simultaneously. Storing the complete word on its end node means no path bookkeeping is needed to emit results.
class TrieNode:
__slots__ = ("children", "word")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.word: str | None = None # set on end nodes
class Solution:
def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
root = TrieNode()
for w in words:
node = root
for ch in w:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = w
m, n = len(board), len(board[0])
out: list[str] = []
def dfs(r: int, c: int, parent: TrieNode) -> None:
ch = board[r][c]
node = parent.children.get(ch)
if node is None:
return
if node.word is not None:
out.append(node.word)
node.word = None # report each word once
board[r][c] = "#"
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != "#":
dfs(nr, nc, node)
board[r][c] = ch
for r in range(m):
for c in range(n):
dfs(r, c, root)
return out
Walkthrough of the first example — board [["a","b"],["c","d"]], words ["abdc","bd","acb"]. The trie has root children a and b. Start at (0,0) 'a': root has child a, descend, mark (0,0). Neighbor (0,1) 'b': the a node has child b (from "abdc"), descend. Neighbor (1,1) 'd': child d exists, descend. Neighbor (1,0) 'c': child c exists, and that node has word = "abdc" → emit it and clear the marker. Backtrack all the way; the acb branch dies at (1,0)→(0,1) because those cells are never adjacent — the DFS simply never offers b after c from that geometry. Start at (0,1) 'b': root has child b, descend; neighbor (1,1) 'd' → node with word = "bd" → emit. Result: ["abdc", "bd"].
Complexity: building the trie is O(total characters) = O(3·10^5). The search is O(m·n · 4 · 3^(L-1)) with L ≤ 10 — about 144 · 4 · 3^9 ≈ 1.1·10^7 board steps, independent of the number of words. Space: O(total characters) for the trie plus O(L) recursion depth.
Approach 3 — Trie + pruning found/dead branches (the full-marks version)
The insight: once a word has been emitted, and once a trie node has no children left, that node can never contribute another match — so delete it from its parent. The trie physically shrinks as words are found, and later DFS starts terminate at the root immediately. On adversarial inputs (many words sharing long prefixes that all get found early) this prunes an enormous amount of re-exploration; it is the difference between passing and TLE-ing on LeetCode’s worst tests.
class TrieNode:
__slots__ = ("children", "word")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.word: str | None = None
class Solution:
def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
root = TrieNode()
for w in words:
node = root
for ch in w:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = w
m, n = len(board), len(board[0])
out: list[str] = []
def dfs(r: int, c: int, parent: TrieNode) -> None:
ch = board[r][c]
node = parent.children.get(ch)
if node is None:
return
if node.word is not None:
out.append(node.word)
node.word = None
board[r][c] = "#"
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != "#":
dfs(nr, nc, node)
board[r][c] = ch
if not node.children and node.word is None:
del parent.children[ch] # prune exhausted branch
for r in range(m):
for c in range(n):
dfs(r, c, root)
return out
Tracing the same example: after "abdc" is emitted, the backtracking unwind deletes the now-childless c, d, b, a nodes of that branch one by one — so when the loop later starts DFS at (1,0) 'c' or (1,1) 'd', the root has no such child and the call returns instantly. Same worst-case bound as Approach 2, O(m·n · 4 · 3^(L-1)) time, but far faster in practice; space is unchanged at O(total characters), shrinking as words are found.
Common pitfalls
- Forgetting to un-mark the cell (
board[r][c] = ch) on the way out of the DFS — later paths through that cell then fail silently.
- Emitting duplicates: without
node.word = None (or a result set), a word reachable from two starting cells is reported twice.
- Checking
node.word only at the end of the recursion instead of at every node — words that are prefixes of other words ("eat" inside "eater") get missed.
- Pruning a node that still holds an unreported word: the delete condition must be
not node.children and node.word is None.
Pattern takeaway
When you must match many patterns against one search space, don’t run the search per pattern — merge the patterns into a trie and run the search once, advancing a trie pointer in lockstep with the exploration. The trie acts as a shared, incrementally-checked filter: one failed prefix kills thousands of words at once, and pruning spent branches makes the filter cheaper the longer the search runs. This “trie as a co-traveling guide for DFS” move reappears in stream matching, autocomplete, and any grid-plus-dictionary problem.