Problem overview
findWords receives a grid of lowercase letters, board, as an Array[Array[Char]], and an Array[String] of words. It returns, as a List[String], every word that can be traced on the board. A word is traced along 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. Every word is reported once, however many paths spell it.
On the board oaan / etae / ihkr / iflv with the words oath, pea, eat and rain, the words found are eat and oath. There is no p on the board, and no a touches the r. On the board ab / cd, abdb would need the b twice, and ad would need a diagonal step, so nothing is found.
Approach: search the board once, guided by a trie
The direct way is to search the board separately for each word. With up to 30,000 words, many of them starting alike (see, seen), that repeats the same path-following over and over.
A trie fixes this. It is a tree in which each node stands for a prefix: a node's children are keyed by the next letter, and the path from the root spells a prefix. All the words go into one trie first. Then a depth-first search starts from each cell and moves to a neighbour only if the trie has a child for that cell's letter. One search from one cell looks for every word at once, and a path that doesn't continue any word is cut off immediately.
Two details keep the answer correct:
- Marking cells. While a path is being extended, its cells must not be reused. The search overwrites the current cell with
'#', which no word contains, and writes the letter back when it leaves the cell. This is backtracking. - Reporting once. The node where a word ends stores the word itself. When a path reaches that node, the search adds the word to the answer and clears the stored word, so a second path to the same word finds nothing to add.
Step by step
- The trie node.
TrieNodegets aval children, amutable.Map[Char, TrieNode]()from the next letter to the child node. Avalonly means the field always refers to the same map, and the map itself can grow. - The word slot. It also gets
var word: String = null, which holds the whole word on the node where a word ends. The search needs the word itself to add it to the answer. - The root. In
findWords,rootis a newTrieNode. It stands for the empty prefix, and every word starts there. - Insert every word. A
forloop goes overword <- words. - Start at the root. Inside it,
var node = root. - Walk the letters. A second loop goes over each character
cofword. - Create missing paths. If
node.childrendoesn't containc, store a newTrieNodeunder it. - Move down:
node = node.children(c). - Mark the end. After the letter loop, set
node.word = word. - The answer buffer. After the insertion loop, create
found, an emptymutable.ArrayBuffer[String](). Every search adds to this one list. - Every row. A loop with
row <- 0 until board.length. - Every column. Inside it,
col <- 0 until board(0).length. All rows have the same length, so the first row gives the number of columns. - Start a search with
dfs(board, row, col, root, found). - Return the result with
found.toList. - The helper's first check.
dfsreturns at once when the cell is off the board. The four recursive calls step to the neighbours without checking them, so this check catches the ones that land outside. - Read the cell:
val letter = board(row)(col). It is needed again at the end to put the cell back. - Prune. If
node.childrendoesn't containletter, return: no word continues this way. A used cell holds'#', which no node has as a child, so this check also stops a path from reusing a cell. - Go down the trie:
val child = node.children(letter). - A word ends here? If
child.wordis notnull, the path spells it. - Record it with
found += child.word. - Clear it with
child.word = null, so other paths to the same word add nothing. - Mark the cell by setting
board(row)(col)to'#'. - Down and up. Call
dfswithrow + 1androw - 1, the samecol, andchildas the node. The path now includes this cell, so its neighbours continue fromchild. - Right and left. Call
dfswithcol + 1andcol - 1. - Undo the mark:
board(row)(col) = letter, so the cell is free for other paths.
The solution in Scala
The lesson's file already has import scala.collection.mutable at the top, which is why the code can write mutable.Map. In a file of your own, add that import first.
class TrieNode {
val children = mutable.Map[Char, TrieNode]()
var word: String = null
}
class Solution {
def findWords(board: Array[Array[Char]], words: Array[String]): List[String] = {
val root = new TrieNode()
for (word <- words) {
var node = root
for (c <- word) {
if (!node.children.contains(c)) {
node.children(c) = new TrieNode()
}
node = node.children(c)
}
node.word = word
}
val found = mutable.ArrayBuffer[String]()
for (row <- 0 until board.length) {
for (col <- 0 until board(0).length) {
dfs(board, row, col, root, found)
}
}
return found.toList
}
def dfs(board: Array[Array[Char]], row: Int, col: Int, node: TrieNode, found: mutable.ArrayBuffer[String]): Unit = {
if (row < 0 || row >= board.length || col < 0 || col >= board(0).length) {
return
}
val letter = board(row)(col)
if (!node.children.contains(letter)) {
return
}
val child = node.children(letter)
if (child.word != null) {
found += 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
}
}
Scala details worth knowing:
- Arrays of arrays.
board(row)(col)reads a cell, andboard(row)(col) = '#'writes one. ACharis written with single quotes,'#', and a string with double quotes.Arrayis mutable, which is what lets the search mark and restore cells in place. - Looping over a string.
for (c <- word)visits the characters of aStringasCharvalues. - Map access.
node.children(c) = new TrieNode()stores a value, andnode.children(c)reads one. Reading a missing key throws aNoSuchElementException; the code always checkscontainsfirst.children.get(c)would return anOptioninstead. nullas "no word".var word: String = nullis a normalStringreference that points at nothing, andchild.word != nullcompares it safely.- Result order.
foundis filled in the order the search meets the words, so the list isn't sorted: on the first example it isList(oath, eat). Sort it with.sortedif you need alphabetical order. - The board is restored. Every cell is set back to its letter on the way out, so after
findWordsthe board is the same as before the call.
Complexity
Time: O(R * C * 4^L) plus the trie build. With L the length of the longest word, a search goes at most L cells deep and tries up to four neighbours at each step, and it starts from each of the R * C cells. The bound doesn't depend on the number of words, because the trie prunes every path that doesn't start some word. Building the trie costs one step per letter of all the words together.
Space: the trie holds at most one node per letter of all the words, and the recursion is at most L frames deep. The answer list holds at most one entry per word.
Edge cases and common mistakes
- The same word along several paths. On
see / net,seecan be traced two ways, yet it appears once. Clearingchild.wordis what does that. - A word that is the start of another.
seeandseenshare a path. The search recordsseewhen it reaches the secondeand keeps going to findseen. Returning right after a hit would lose the longer word. - Forgetting to restore the cell. If the letter isn't written back, the board is damaged for every later search, and words are missed. Restoring has to happen on every exit after the mark, which here is the single line at the end.
- Reusing a cell. Without the
'#'mark, a path could go back to a cell it already used: onab / cd,abdbwould wrongly be found. - Diagonal steps. Only the four direct neighbours count. In
ab / cd,aanddtouch only at a corner, soadisn't found. - One-cell boards and repeated letters. On the board
a, the wordais found. Onaa, the wordsaaa,aandaagiveaandaa: the third letter would need a third cell. - Checking the bounds after reading. Reading
board(row)(col)first and testing the indexes afterwards throws anArrayIndexOutOfBoundsExceptionon the edges. The bounds check comes first.
Testing
Results from running the solution, sorted alphabetically:
| board | words | Result |
|---|---|---|
oaan / etae / ihkr / iflv | oath, pea, eat, rain | eat, oath |
ab / cd | abdb, ad | none |
see / net | see, seen, set, net, tee, teen | net, see, seen, tee |
a | a | a |
aa | aaa, a, aa | a, aa |
ab | ab, ba | ab, ba |
