Given an m x n board of lowercase letters and a list of words, return every word from the list that can be formed by a path on the board.
A word is formed by starting on any cell and stepping to horizontally or vertically adjacent cells, spelling the word in order. The same cell may not be used more than once within a single word. Each word in the answer must appear in the input list, and the answer must contain no duplicates. The words may be returned in any order.
For example, on the board
o a a n
e t a e
i h k r
i f l v
with words = ["oath", "pea", "eat", "rain"], the answer is ["oath", "eat"]: "oath" traces o(0,0) → a(0,1) → t(1,1) → h(2,1), and "eat" traces e(1,3) → a(1,2) → t(1,1). "pea" and "rain" cannot be traced on the board.
Example
"oath" and "eat" trace valid adjacent paths; "pea" and "rain" cannot.
Constraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 12
- board[i][j] is a lowercase English letter.
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters.
- All strings in words are distinct.
Intuition
The obvious approach searches each word independently: for every word in the list, scan the board for a starting cell and run a depth-first search that tries to spell it out, stepping only to adjacent cells and never reusing a cell within one path.
function findWords(board, words) {
const rows = board.length, cols = board[0].length;
const found = [];
// Try to spell word[k..] starting at cell (r, c).
const dfs = (r, c, word, k) => {
if (k === word.length) return true; // whole word spelled
if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
if (board[r][c] !== word[k]) return false; // letter mismatch
const ch = board[r][c];
board[r][c] = "#"; // mark visited
const ok = dfs(r + 1, c, word, k + 1) || dfs(r - 1, c, word, k + 1)
|| dfs(r, c + 1, word, k + 1) || dfs(r, c - 1, word, k + 1);
board[r][c] = ch; // restore (backtrack)
return ok;
};
for (const word of words) {
let here = false;
for (let r = 0; r < rows && !here; r++)
for (let c = 0; c < cols && !here; c++)
if (dfs(r, c, word, 0)) here = true;
if (here) found.push(word);
}
return found;
}That re-walks the entire board once per word, and two words sharing a prefix ("oath", "oats") re-trace that prefix's paths from scratch. With W words it's O(W · m·n · 4^L). Can we do better?
The key observation: flip the loop. Instead of asking "where is each word?", build a trie of all the words, then DFS the board once, walking the board and the trie in lockstep — at cell (r, c) you may only descend trie child board[r][c]. The moment the trie has no such child, that branch is dead and every word sharing that prefix is pruned together. When the walk reaches a trie node that ends a word, record it. This is backtracking steered by the trie.
The walk happens on the 2-D board, so the diagram below is a gridWalkthrough: it traces one productive path spelling "oath", then a dead branch the trie prunes. Visited cells are marked; the cell under the cursor is the current trie/board step. Walking it through:
board scan steered by a trie of ["oath", "eat"] — one path spells "oath", a dead branch prunes
Begin a DFS at every cell. At (0,0)='o' the trie has an 'o' edge (the start of "oath"), so descend.
Step right to (0,1)='a'. The trie node for 'o' has an 'a' child, so the prefix "oa" is still alive.
Down to (1,1)='t'. "oat" is a valid trie path — keep going toward a possible word end.
Down to (2,1)='h'. The trie node for "oath" is flagged as a word end — collect "oath" and clear its flag so it can't be reported twice.
A different branch from "oa": cell (0,2)='a' would extend to "oaa", but the trie has no such path — prune the whole branch at once.
A fresh start at (1,3)='e': the trie's other word "eat" traces e(1,3)→a(1,2)→t(1,1), ending on a flagged node — collect "eat".
Optimization
Trie of words + DFS backtracking from each cell
Searching every word independently re-walks the board once per word. Instead, build a trie of all the words, then do a single DFS from every cell that walks the board and the trie in lockstep: at cell (r, c) you can only continue down trie child board[r][c]. The moment the path can't extend in the trie, that whole branch is dead — every word sharing that prefix is pruned at once.
When the DFS reaches a trie node whose word field is set, that word is fully spelled on the board, so record it. To avoid reusing a cell within one path, temporarily overwrite the visited cell (here with "#") and restore it on the way back out — standard backtracking.
A neat trick keeps the result duplicate-free without a separate set: clear the trie node's word field once collected, so it can't be reported twice. Pruning empty branches keeps the search close to the board size times the trie depth rather than blowing up per word.
function findWords(board, words) {
// Build a trie of all target words; each end node stores the whole word.
const root = {};
for (const word of words) {
let node = root;
for (const ch of word) {
node[ch] = node[ch] || {};
node = node[ch];
}
node.word = word; // mark the end of a complete word
}
const rows = board.length;
const cols = board[0].length;
const found = [];
const dfs = (r, c, node) => {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
const ch = board[r][c];
const next = node[ch];
if (!next) return; // no trie branch for this letter → dead path, prune
if (next.word) {
found.push(next.word);
next.word = null; // collected once; clearing it avoids duplicate reports
}
board[r][c] = "#"; // mark visited so this path can't reuse the cell
dfs(r + 1, c, next);
dfs(r - 1, c, next);
dfs(r, c + 1, next);
dfs(r, c - 1, next);
board[r][c] = ch; // restore for other paths (backtrack)
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root); // try starting a word at every cell
}
}
return found;
}Complexity analysis
Time complexity: O(W·L + m·n·4^Lmax). Here's why:
- Building the trie costs the total length of all words,
O(W · L). - The single board DFS starts from each of
m·ncells and can branch in 4 directions up to the longest word's lengthLmax— but the trie prunes any branch with no matching child, so in practice it explores far less than the bound.
The win over the brute force is the shared prefix pruning: words sharing a prefix are walked together, not re-traced per word, so the W factor leaves the exponential term.
Space complexity: O(W·L). Here's why:
- The trie holds at most one node per character across all words —
O(W · L). - The DFS recursion stack is at most
O(Lmax)deep, and the board is mutated in place (cells restored on backtrack), so no copy is made.
So the dominant extra space is the O(W·L) trie; the result list holds only the found words.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| board = a | ["a"] | Single cell matches a single-letter word. |
| board = ab cd | [] | No words to find — empty result. |
| board = ab cd | ["abdc"] | A word that turns a corner: a→b→d→c. |
| board = aa | ["aa"] | Cell reuse is forbidden, so "aaa" can't be formed from two cells. |
| board = ab cd | ["ab"] | Diagonal is not adjacency — "ad" fails, the horizontal "ab" succeeds. |
| board = oaan etae ihkr iflv | ["oath","eat"] | The canonical board: two of four words trace valid paths. |
Try it yourself
Write your solution against the real judge before checking the reference.