TL;DR
Build a trie of all the words, then run one backtracking DFS per board cell that walks the board and the trie in lockstep, pruning trie nodes as words are found. Time is O(m·n · 4 · 3^(L-1)) for max word length L; space is O(total word characters).
Approach 1 — Brute force (Word Search I, once per word)
Run the classic single-word backtracking search independently for every word in the list.
def findWords(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 (a path never steps back the way it came). Multiplied by 3·10^4 words, the worst case is roughly 3·10^4 · 144 · 3^9 ≈ 8·10^10 steps. The per-word repetition is what the constraints rule out.
Approach 2 — Trie + one shared backtracking DFS
A DFS path through the board spells a string one letter at a time, and a trie answers in O(1) whether any word in the list continues with the next letter. So instead of asking “does word w exist?” once per word, walk the board once while advancing a trie pointer alongside the board pointer: when the trie has no child for a neighbor’s letter, every word sharing that prefix is eliminated at once. Storing the complete word on its end node means no extra path bookkeeping is needed to emit results.
All words share one trie. For ["abdc", "bd", "acb"] the trie is:
flowchart TD
root((root)) --> a((a))
root --> b((b))
a --> ab((b))
ab --> abd((d))
abd --> abdc["c · abdc"]
a --> ac((c))
ac --> acb["b · acb"]
b --> bd["d · bd"]
Nodes marked with a word are end nodes; the DFS emits that word when it reaches one.
class TrieNode:
__slots__ = ("children", "word")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.word: str | None = None # set on end nodes
def findWords(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 and 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 has word = "abdc", so emit it and clear the marker. Backtrack fully. The acb branch never fires: spelling acb needs c then b, but the c at (1,0) and the b at (0,1) are diagonal, so the DFS never reaches b after c. Start at (0,1) 'b': root has child b, descend; neighbor (1,1) 'd' has word = "bd", so 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
Once a word has been emitted and a trie node has no children left, that node can never contribute another match, so delete it from its parent. The trie 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 avoids a large amount of re-exploration, and is often the difference between an accepted solution and a time-limit exceeded on LeetCode’s worst tests.
class TrieNode:
__slots__ = ("children", "word")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.word: str | None = None
def findWords(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, and a nodes of that branch one by one. When the loop later starts DFS at (1,0) 'c' or (1,1) 'd', the root has no such child and the call returns immediately. The worst-case bound matches Approach 2 at O(m·n · 4 · 3^(L-1)) time, but it is faster in practice; space is unchanged at O(total characters) and shrinks 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, do not run the search once 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 eliminates thousands of words at once, and pruning spent branches makes the filter cheaper the longer the search runs. Advancing a trie pointer alongside a DFS reappears in stream matching, autocomplete, and any grid-plus-dictionary problem.