Problem overview
findWords receives a grid of lowercase letters, board, and an array of strings, words. It returns every word that can be traced on the board. A word is traced by a path of cells: the first letter is in some cell, and each next letter is in a cell directly above, below, left or right of the previous one (no diagonals). A cell can be used only once within one word. Each word is reported once, in any order, and the result is empty when nothing can be traced.
For the board oaan / etae / ihkr / iflv and the words ["oath", "pea", "eat", "rain"], the answer is ["eat", "oath"] once sorted. "oath" goes from the top-left o right to a, then down twice to t and h. There is no p on the board, and no a touches the r.
Approach: one search for all the words
The direct method runs a path search from every cell for every word. That repeats a lot: "oath" and "oat" share their first three cells, but each gets its own walk. With up to 30,000 words, the repeated work adds up.
A trie removes the repetition. It stores all the words as paths of letters from a shared root, so words with the same beginning share the same nodes. We then run one depth-first search from each cell, and at every step follow the trie as well as the board. If the current letter isn't a child of the current trie node, no word continues this way and the search backs off immediately. When we reach a node where a word ends, we report it.
Words are at most L letters long, so a path goes at most L cells deep and branches in at most four directions: O(R · C · 4^L) in the worst case, plus the time to build the trie, however many words there are.
Step by step
- Trie node.
TrieNodehaschildren, aRecord<string, TrieNode>(an object from letters to nodes) that starts as{}, andword, astring | nullthat starts asnull. A node where a word ends stores the word itself instead of a flag, so the search can report it the moment a path arrives. - Build the trie. Create
root, the node of the empty prefix. For each word, startnodeatrootand walk down one letter at a time. If the letter isn't innode.children, create a child for it. Then move to that child. After the last letter, setnode.word = word. - The answer list. Create
found, an emptystring[]that all the searches add to. - Start everywhere. Loop over every
rowand everycol, usingboard[0].lengthfor the number of columns, and callthis.dfs(board, row, col, root, found). Sincerootholds all the words, one call looks for all of them. After the loops, returnfound. - Off the board. In
dfs, return when the row or column is out of range. The recursive calls step to all four neighbours without checking, so some of them land outside. - Follow the trie. Read the cell's
letter. If it isn't innode.children, return: no word continues this way. Otherwise move down:child = node.children[letter]. - Report a word. If
child.word !== null, push it ontofoundand setchild.wordback tonull. A word can often be traced along several paths, and clearing it means the next path adds nothing, so each word appears once. - Mark the cell. Set
board[row][col] = '#'. No word contains#, so a path that comes back to this cell stops at the check onnode.children. That enforces "each cell once per word". - Explore. Call
dfsfor the cell below, above, right and left, each time passingchildas the node, because the path now includes this cell. - Backtrack. Put the letter back:
board[row][col] = letter. The cell is free for other paths.
The solution in TypeScript
class TrieNode {
children: Record<string, TrieNode> = {};
word: string | null = null;
}
class Solution {
findWords(board: string[][], words: string[]): string[] {
const root: TrieNode = new TrieNode();
for (const word of words) {
let node: TrieNode = root;
for (const c of word) {
if (!(c in node.children)) {
node.children[c] = new TrieNode();
}
node = node.children[c];
}
node.word = word;
}
const found: string[] = [];
for (let row = 0; row < board.length; row++) {
for (let col = 0; col < board[0].length; col++) {
this.dfs(board, row, col, root, found);
}
}
return found;
}
dfs(board: string[][], row: number, col: number, node: TrieNode, found: string[]): void {
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
return;
}
const letter: string = board[row][col];
if (!(letter in node.children)) {
return;
}
const child: TrieNode = node.children[letter];
if (child.word !== null) {
found.push(child.word);
child.word = null;
}
board[row][col] = '#';
this.dfs(board, row + 1, col, child, found);
this.dfs(board, row - 1, col, child, found);
this.dfs(board, row, col + 1, child, found);
this.dfs(board, row, col - 1, child, found);
board[row][col] = letter;
}
}
TypeScript details
Record<string, TrieNode>is an ordinary object used as a dictionary. Theinoperator tests whether a key exists, and it also sees keys inherited fromObject.prototype. That is harmless here because every key is a single letter or#, and no inherited property has a one-character name.for (const c of word)walks a string character by character. For lowercase English letters, that is one letter per step.child.word !== nullcompares withnullexplicitly. An empty string would be falsy, but the words here are never empty, and the explicit test says what it means.- The method modifies
boardwhile searching and restores every cell it changes, so the grid is the same after the call. Running the solution on the lesson's examples leaves each board unchanged. - Types are erased at run time.
string[][]checks nothing about what is in the grid; the solution relies on the cells being one-letter strings. foundlists words in the order the search meets them, which is not alphabetical. For the first example the raw result is["oath", "eat"]. Sort the result, for instance with[...found].sort()(strings sort correctly with the default comparator), if you need alphabetical order.
Complexity
Time: building the trie takes O(W · L) for W words of up to L letters. The search starts from R · C cells. Each path is at most L cells long and each step has at most four directions to try (three after the first, since the cell we came from is marked), so O(R · C · 4^L) is a safe bound. In practice the trie cuts most branches early, because a path survives only while it spells the start of some word.
Space: the trie has at most W · L nodes. The recursion goes at most L deep, and the marking trick needs no extra visited grid.
Edge cases and common mistakes
- Forgetting to restore the cell. Without
board[row][col] = letter, cells stay marked as#and later paths fail. - Reusing a cell in a word. On the board
ab / cd, the wordabdbwould need thebtwice. The marker blocks this, so the result is empty. - Diagonal neighbours. On that same board,
aanddtouch only at a corner, soadis not found. - Duplicates in the answer. On the board
see / net, the wordseehas two paths. Clearingchild.wordafter the first report keeps it in the result once. - A word that is a prefix of another.
seeandseenshare nodes, and both are found: the word is reported when the path reaches its node, and the search continues past it. - Very short boards. On a 1 by 1 board holding
a, the wordais found. On the boardaa, the wordsaaa,aaandagiveaaanda, since only two cells exist.
Testing
The solution's results, sorted, for a few boards (rows written as strings):
| Board | Words | Result |
|---|---|---|
oaan, etae, ihkr, iflv | oath, pea, eat, rain | ["eat","oath"] |
ab, cd | abdb, ad | [] |
see, net | see, seen, set, net, tee, teen | ["net","see","seen","tee"] |
a | a | ["a"] |
aa | aaa, aa, a | ["a","aa"] |
A 12 by 12 board of a with the words aaaaaaaaaa (ten letters) and aaaaaaaaa (nine) also finishes in about a tenth of a second and finds both.
