Problem overview
findWords receives a grid of letters, board, with R rows and C columns, and a list of distinct 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, each next letter is in a cell directly above, below, left or right of the previous one (no diagonals), and a cell can be used only once within one word. Each word that can be traced is returned once.
In the first example, the board is
o a a n
e t a e
i h k r
i f l v
and the words are ["oath", "pea", "eat", "rain"]. The answer is "oath" and "eat". "oath" starts at the top-left o, goes right to a, then down twice to t and h. The board has no p, and no a touches the r, so "pea" and "rain" cannot be traced. The returned list is ['oath', 'eat']: it holds the words in the order the search meets them, so sort it if you need alphabetical order.
Approach: one search for all words, guided by a trie
The plain method searches the board separately for each word with a depth-first search (DFS). With up to 30,000 words, many of them starting the same way ("tea", "team", "tear"), the same paths are walked again and again.
A trie removes that repetition. It is a tree where each edge is a letter and each path from the root spells a prefix of some word. Words that share a beginning share their path. Searching the board with the trie as a guide means: stand on a cell, and continue only if the trie node you came from has a child for this cell's letter. A path that no word continues is dropped at once, and one search from each cell looks for every word together.
Each node of the trie stores, in word, the complete word that ends there (or None). Keeping the word itself, rather than a yes/no flag, means the search can add it to the answer the moment a path reaches that node. Setting it back to None afterwards makes sure a word that can be traced along several paths is added only once.
The search marks the cell it stands on as used by writing '#' into it, which matches no word, and puts the letter back when it leaves the cell. That is backtracking: try a path, then undo the mark so other paths can use the cell.
Step by step
The trie node and the trie
- Children. In
TrieNode.__init__, createself.children = {}. It maps a letter to the child node for that letter, and holds only letters some word uses. - The word that ends here. Set
self.word = None. - Create the root in
findWords:root = TrieNode(). It stands for the empty prefix. - Insert every word with a loop over
words. - Start at the root for each word:
node = root. - Walk the letters with an inner loop over the characters
cof the word. - Create the missing step. If
cis not innode.children, store a newTrieNode()under it. - Move down:
node = node.children[c]. - Mark the end. After the letter loop, set
node.word = word.
Starting the searches
- The answer list:
found = []. Every search adds to this same list. - Loop over the rows with
range(len(board)), and - over the columns with
range(len(board[0])), since all rows have the same length. - Search from each cell with
self.dfs(board, row, col, root, found). - Return
foundafter both loops.
The helper dfs
- Leave the board. If
roworcolis outside the grid, return. The calls below step to all four neighbours without checking, so cells on the edge send some calls off the board. - Remember the letter:
letter = board[row][col]. It is needed again at the end to restore the cell. - Prune. If
letteris not innode.children, no word continues this path, so return. A used cell holds'#', which is never a child, so it is rejected here too. - Step down the trie:
child = node.children[letter]. - Check for a word. If
child.wordis notNone, the path spells a whole word. - Record it with
found.append(child.word), and - clear it with
child.word = None, so the same word is not added again by another path. - Mark the cell as used:
board[row][col] = '#'. - Search down and up:
self.dfswithrow + 1androw - 1, passingchildas the node. - Search right and left with
col + 1andcol - 1. - Restore the cell:
board[row][col] = letter.
The solution in Python
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
found = []
for row in range(len(board)):
for col in range(len(board[0])):
self.dfs(board, row, col, root, found)
return found
def dfs(self, board: List[List[str]], row: int, col: int, node: TrieNode, found: List[str]) -> None:
if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
return
letter = board[row][col]
if letter not in node.children:
return
child = node.children[letter]
if child.word is not None:
found.append(child.word)
child.word = None
board[row][col] = '#'
self.dfs(board, row + 1, col, child, found)
self.dfs(board, row - 1, col, child, found)
self.dfs(board, row, col + 1, child, found)
self.dfs(board, row, col - 1, child, found)
board[row][col] = letter
Python details worth a closer look:
- Dict as the child table.
c not in node.childrenis a constant-time test, andnode.children[c]is safe once it has passed. For the words "oath", "eat", "see" and "seen", the root's children areo,eands, and the node for "se" has just one child,e, shared by "see" and "seen". - Lists are mutable.
boardis a list of lists, anddfschanges it in place. That is why the cell must be restored: the same board object is seen by every call. AfterfindWordsreturns, the board is exactly as it was. - Strings are immutable, which is why the board is given as a list of one-character strings and not as strings:
board[row][col] = '#'would fail on a string row. foundis shared. The same list object is passed to every call, soappendin a deep call is visible tofindWords.is not Noneis the right test forchild.word, because a stored word is a non-empty string and the marker for "no word" isNone.
Complexity
Time: O(R · C · 4^L) plus the cost of building the trie, where L is the length of the longest word (at most 10). A search from one cell goes at most L cells deep and tries up to four neighbours at each step, so it is bounded by 4^L. In practice it is far less: a path is dropped as soon as the trie has no child for its letter, and a cell cannot be used twice in one path. Building the trie takes time proportional to the total number of letters in words. The search cost does not depend on the number of words.
Space: the trie holds at most one node per letter of all the words, and the recursion is at most L calls deep, so the extra space is proportional to the total length of the words plus L, apart from the answer list.
Edge cases and common mistakes
- A word that can be traced in several ways. On the board
["see", "net"], "see" can end on the cell to the right or on the cell below. Clearingchild.wordafter the first hit keeps it in the answer once. - Words that start the same way. "see" and "seen" share a path, and the node for "see" holds a word and also has a child. The search records "see" and then keeps going, so "seen" is found too. Returning right after a hit would lose "seen".
- Reusing a cell. On
["ab", "cd"], "abdb" would need theba second time, so it is not found. Without the'#'mark it would be. - Diagonal neighbours.
aanddin the same board touch only at a corner, so "ad" is not found. - Forgetting to restore the letter. Cells stay
'#'and later searches from other cells miss words. - A one-cell board.
[["a"]]with the words["a"]gives['a']. The loops and the bounds check handle it without special cases. - Order of the result. The list comes out in the order the search meets the words, not alphabetically. Wrap it in
sorted(...)if you compare it with an alphabetical list.
Testing
- The board
["oaan", "etae", "ihkr", "iflv"]with["oath", "pea", "eat", "rain"]gives['oath', 'eat'], which is['eat', 'oath']once sorted. - The board
["ab", "cd"]with["abdb", "ad"]gives[]. - The board
["see", "net"]with["see", "seen", "set", "net", "tee", "teen"]gives['see', 'seen', 'net', 'tee'], sorted['net', 'see', 'seen', 'tee']. - The board
["aa"]with["a", "aa", "aaa"]gives['a', 'aa']: "aaa" needs three cells. - The board
["ab"]with["ba", "ab"]gives['ab', 'ba']: a word can be traced in either direction along a row.
In each test, the rows above are strings written out for brevity: the function receives them as lists of single letters, such as [["a", "b"], ["c", "d"]].
