Problem overview
FindWords receives a grid of letters, char[][] board, and a string[] words. It returns, as an IList<string>, 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 reported once, however many paths spell it. The lesson's tests list the answer in alphabetical order.
On the board with rows oaan, etae, ihkr, iflv and the words oath, pea, eat, rain, the answer is eat and oath. There is no p on the board, and no a is next to the r, so the other two can't be traced. On the board ab / cd, the word abdb fails because it would reuse the cell b, and ad fails because a and d touch only at a corner.
Approach: one search for all the words
The simple plan is to search the board once per word: start a depth-first search at every cell and try to spell that word. It works, but words that begin the same way, like see, seen and set, repeat the same paths again and again, and the lesson allows up to 30,000 words.
A trie (prefix tree) stores all the words so that words with a common beginning share one path from the root. Walk the board and the trie together: a search from a cell may step onto a neighbour only if the trie has a child for that neighbour's letter. Paths that start no word are cut off immediately, and one search from each cell looks for every word at once. With words of at most L letters, a search goes at most L cells deep and branches at most 4 ways, so the board work is O(R * C * 4^L) in the worst case, whatever the number of words. Building the trie costs time proportional to the total number of letters in the words.
Step by step
- Trie node field
children: apublicDictionary<char, TrieNode>, created empty. It maps each next letter to its child node. Fields are private unless markedpublic, andSolutionmust reach it. - Trie node field
word: apublic string, set tonull. On the node where a word ends it holds the word itself, so the search can add it to the answer the moment it gets there. - Create the root:
TrieNode root = new TrieNode(). It stands for the empty prefix. - Insert every word with a
foreachoverwords. For each one, startnodeatrootand walk its letters with an innerforeach. - For each letter, if
node.childrenhas no keyc(ContainsKey), store a newTrieNodeunder it; then move down withnode = node.children[c]. - After the letters, set
node.word = word. - Collect results in
List<string> found, a new empty list. AList<string>is anIList<string>, so it can be returned as is. - Start a search from every cell: loop
rowfrom 0 whilerow < board.Length, andcolfrom 0 whilecol < board[0].Length, callingDfs(board, row, col, root, found). Returnfoundat the end. - In
Dfs, leave the board: ifroworcolis outside the grid, return. The four neighbour calls below don't check their targets, so edge cells send some calls off the board. - Read the letter:
char letter = board[row][col]. It is needed again at the end. - Stop if the trie can't continue: if
node.childrenhas no keyletter, return. This check keeps the search small. - Step down the trie:
TrieNode child = node.children[letter]. - A word ends here: if
child.wordis notnull,Addit tofoundand setchild.wordback tonull. A word can often be traced along several paths, and clearing it means it is added only once. - Mark the cell as used by setting
board[row][col]to'#'. No word contains#, so a path that comes back to this cell stops at thechildrencheck. - Search the four neighbours (row + 1, row - 1, col + 1, col - 1), each time passing
child, notnode, because the path now includes this cell. - Put the letter back:
board[row][col] = letter. The cell is free again for other paths. Undoing the mark on the way out is what makes this backtracking.
The solution in C#
class TrieNode {
public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
public string word = null;
}
class Solution {
public IList<string> FindWords(char[][] board, string[] words) {
TrieNode root = new TrieNode();
foreach (string word in words) {
TrieNode node = root;
foreach (char c in word) {
if (!node.children.ContainsKey(c)) {
node.children[c] = new TrieNode();
}
node = node.children[c];
}
node.word = word;
}
List<string> found = new List<string>();
for (int row = 0; row < board.Length; row++) {
for (int col = 0; col < board[0].Length; col++) {
Dfs(board, row, col, root, found);
}
}
return found;
}
void Dfs(char[][] board, int row, int col, TrieNode node, List<string> found) {
if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length) {
return;
}
char letter = board[row][col];
if (!node.children.ContainsKey(letter)) {
return;
}
TrieNode child = node.children[letter];
if (child.word != null) {
found.Add(child.word);
child.word = null;
}
board[row][col] = '#';
Dfs(board, row + 1, col, child, found);
Dfs(board, row - 1, col, child, found);
Dfs(board, row, col + 1, child, found);
Dfs(board, row, col - 1, child, found);
board[row][col] = letter;
}
}
C# details worth knowing:
char[][]is a jagged array: an array of rows, each row achar[], indexedboard[row][col].board.Lengthis the number of rows, andboard[0].Lengththe number of columns of the first row. Don't confuse it withchar[,], which is indexedboard[row, col].charis a single UTF-16 code unit, written with single quotes ('#'). Aforeachover astringyields itscharvalues, which is how the insert loop reads a word.- Reading a missing key throws.
node.children[c]on an absent key raisesKeyNotFoundException. Both lookups in the code come right after aContainsKeycheck or the insertion of that key.TryGetValuewould do the check and the lookup in one step. - The board is changed in place and restored. Arrays are reference types, so
Dfsworks on the caller's board. Every'#'is replaced by its letter before the call returns, so afterFindWordsthe board is as it was. - The trie is consumed. Setting
child.wordtonullchanges the trie, which is fine because it is local to oneFindWordscall. - The result order follows the search, not the alphabet, so a program that wants sorted output must sort.
found.Sort()sorts the list in place;string.CompareOrdinalorStringComparer.Ordinalsort lowercase letters in plain alphabetical order.
Complexity
Time. Building the trie costs O(total letters in words). Each search starts at one of R * C cells and goes down paths of at most L cells, where L is the longest word, with at most 4 choices at the first cell and 3 afterwards (the cell just left is marked). That bounds the board work by O(R * C * 4^L). In practice the trie cuts most branches early, since a path continues only while it is a prefix of some word.
Space. The trie takes O(total letters in words) in the worst case. The recursion is at most L deep. The answer list holds at most one entry per word.
Edge cases and common mistakes
- Reusing a cell in one word. On the board
ab/cd,abdbreturns nothing and the result is empty, becausebis marked'#'when the path comes back to it. - Diagonal neighbours.
adon the same board is not traced: only four directions count. - The same word along several paths. With the board
see/net, the wordseehas two paths, yet it appears once, thanks to clearingchild.word. - A word that is a prefix of another.
seeandseenboth come out: the search reportsseeat its node and keeps going down the same path. - Forgetting to restore the cell. If
board[row][col]keeps the'#', other paths can no longer cross that cell and words are missed. - Passing
nodeinstead ofchildto the neighbour calls. The next cell would be matched against the same level of the trie, so the search would follow the wrong letters. - A word longer than the number of cells. On a board with one row
aa, the wordaaacan't be traced, because it would need a third cell. - Single cell. On a 1x1 board holding
a, the wordais found.
Testing
Running FindWords on the boards below (answers sorted alphabetically) gives:
| board rows | words | Result |
|---|---|---|
oaan, etae, ihkr, iflv | oath, pea, eat, rain | eat, oath |
ab, cd | abdb, ad | empty |
see, net | see, seen, set, net, tee, teen | net, see, seen, tee |
a | a | a |
aa | aaa | empty |
After searching ab / cd for the word abdc, the board still reads ab / cd.
