Problem overview
findWords(board, words) receives a grid of lowercase letters with R rows and C columns and an array of 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. A cell can be used only once within one word. Each word is returned once, in any order; the tests print the answer in alphabetical order.
With the board oaan / etae / ihkr / iflv (one row per line) and the words ["oath", "pea", "eat", "rain"], the answer is ["eat", "oath"]. "oath" runs from the top-left o right, down, down. "eat" starts at the e at the end of the second row and goes left twice. There is no p, so "pea" fails, and no a touches the r, so "rain" fails.
Approach: one search for all words, guided by a trie
The direct way is to run a path search for each word, which repeats work whenever words share a beginning: "see" and "seen" would walk the same cells twice. A trie (prefix tree) stores all words in one tree where each level is one more letter, so words with the same beginning share their path.
The search then runs once, from every cell, with the trie as its guide. At each cell it asks whether some word continues with this cell's letter. If the current trie node has no child for that letter, the path is a dead end and the search stops at once. The search therefore follows only paths that are the beginning of some word, and it is never deeper than the longest word, L letters. Each cell has at most four directions to try, which gives the bound O(R · C · 4^L) plus the cost of building the trie.
To avoid using a cell twice, the search overwrites the cell with '#' while it explores the neighbours and puts the letter back afterwards. That undo step is what makes it backtracking.
Step by step
- The trie node. In
TrieNode's constructor, setthis.children = {}. It maps a letter to the child node for that letter. - Store the word. Set
this.word = null. On the node where a word ends it holds the word itself rather than a flag, so the search can add it to the answer the moment it arrives. - Create the root in
findWords:const root = new TrieNode(). It stands for the empty prefix. - Insert each word with a
for...ofloop overwords. - Start at the root:
let node = root. - Walk the letters with
for (const c of word). - Create missing children: if
!(c in node.children), store a newTrieNodeinnode.children[c]. - Move down:
node = node.children[c]. The child exists now, new or old. - Mark the end: after the letters,
node.word = word. - Collect results in
const found = []. - Loop over the rows,
rowfrom 0 whilerow < board.length. - Loop over the columns,
colfrom 0 whilecol < board[0].length. Every row has the same length. - Start a search from each cell:
this.dfs(board, row, col, root, found). One search looks for every word at once. - Return
found. - In
dfs, leave the board: ifroworcolis below 0 or past the last row or column, return. The four neighbour calls are made without checking, so this check stops the ones that fall off the edge. - Read the letter:
const letter = board[row][col], needed again at the end. - Prune: if
!(letter in node.children), return, because no word continues this way. - Go down the trie:
const child = node.children[letter]. - A word ends here: if
child.word !== null,pushit ontofound. - Clear it: set
child.word = null, so a second path that spells the same word adds nothing. - Mark the cell:
board[row][col] = '#'. No word contains#, so any path that comes back here stops at the pruning check above. - Below and above: call
this.dfswithrow + 1androw - 1, passingchildas the node. - Right and left: the same with
col + 1andcol - 1. - Undo:
board[row][col] = letter.
The solution in JavaScript
class TrieNode {
constructor() {
this.children = {};
this.word = null;
}
}
class Solution {
findWords(board, words) {
const root = new TrieNode();
for (const word of words) {
let node = 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 = [];
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, row, col, node, found) {
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
return;
}
const letter = board[row][col];
if (!(letter in node.children)) {
return;
}
const child = 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;
}
}
Details worth knowing:
- An object as a map.
c in node.childrenasks whether the object has a keyc. The keys are single lowercase letters, so a plain object is fine here. For general strings,inalso finds inherited names such as"toString", which is the reason to prefer aMapthere. - The board is changed in place. The
'#'marks exist only while a path is being explored, and each one is undone on the way back, so the board has its original letters whenfindWordsreturns. - Found words come in search order. The returned array is not sorted. For the third example it is
["see", "seen", "net", "tee"], and the lesson's tests compare it in alphabetical order. - Clearing
child.worddeduplicates. The trie is changed as words are found, which is why each word appears once even when many paths spell it.
Complexity
Time: O(R · C · 4^L) plus building the trie, which costs the total number of letters in words. A search from one cell goes at most L cells deep, because no trie path is longer than the longest word, and each cell branches into at most four neighbours. In practice the trie prunes most branches, and the number of words does not multiply the search.
Space: the trie holds at most one node per letter of words, and the recursion is at most L calls deep. The board is reused rather than copied.
Edge cases and common mistakes
- Reusing a cell. On the board
ab / cd, "abdb" would need thebtwice and can't be traced. Forgetting the'#'mark would accept it. - Diagonal steps. On the same board "ad" fails, because
aanddtouch only at a corner. - The same word found along several paths. On
see / net, "see" can be traced two ways but is listed once. - One word being the start of another. "see" and "seen" share a path. The word is added when the path reaches its end, and the search continues for the longer word.
- Forgetting to undo the mark. Letters stay replaced by
#and later searches miss words. - Going out of bounds. Without the first check,
board[row]can beundefinedand reading[col]from it throws aTypeError.
Testing
Boards are written one row per string.
["oaan","etae","ihkr","iflv"]with["oath","pea","eat","rain"]finds"eat"and"oath".["ab","cd"]with["abdb","ad"]finds nothing:[].["see","net"]with["see","seen","set","net","tee","teen"]finds"net","see","seen"and"tee".["aa"]with["a","aa","aaa"]finds"a"and"aa": the third word needs three cells.
