Find every word from a list on a letter grid. Build a trie of the words and walk the board once, following only paths the trie allows.
▼The problem
LeetCode 212 (Hard). Given an m × n board of letters and a list of words, return every word that can be traced on the board by a path of horizontally or vertically adjacent cells, using each cell at most once per word.
Example (from the problem statement): the board [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]] with words [oath, pea, eat, rain] → [eat, oath].
The solution
def findWords(board, words):
trie = {}
for w in words:
node = trie
for ch in w: node = node.setdefault(ch, {})
node['$'] = w # a word ends here
R, C, found = len(board), len(board[0]), []
def dfs(r, c, parent):
ch = board[r][c]
node = parent[ch]
if '$' in node: found.append(node.pop('$'))
board[r][c] = '#' # light it
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
dfs(nr, nc, node)
board[r][c] = ch # put it out
if not node: parent.pop(ch) # prune
for r in range(R):
for c in range(C):
if board[r][c] in trie: dfs(r, c, trie)
return foundTranscript
Word Search Two. Given a board of letters and a list of words, find every word you can trace by stepping between neighboring cells, using each cell at most once per word.
The words are oath, pea, eat and rain. Oath starts in the top-left corner, and eat bends around on the right. Pea and rain can't be traced. The answer: eat and oath.
The simple way runs a whole Word Search for every word, walking the same board again and again.
Instead, give the explorer a map: a trie of all the words. Walk the board and the map together, stepping only onto letters the map has a branch for. Reach a word's end: found it. Then erase it from the map, so it's never found twice.
In code, build the trie first. The helper takes a cell and the map node it came from. If a word ends here, record it and remove it. Light the cell, follow each neighbor with a branch, then put the light out. Prune the node if it's empty. Start from every cell.
Let's run it. The top-left O starts oath: A, T, H. Found it! That branch is now empty, so it's erased. The E below has no A beside it. The E on the right steps to A, then T: found eat. The R has no A nearby.
For an m by n board and words up to L letters, each cell starts a walk with at most three new ways per step: m times n times three to the L, once for all the words. The trie stores every letter.
One map, one walk, every word. That's Word Search Two.