Word Search II

Hard#212trie and grid together

There is a grid of letters and a list of words. Return every word that can be spelled by a path of cells touching up, down, left or right, with no cell used twice in one word. Our example: the grid tea / ons and the words toe, tea, ten — the answer is [ten, tea]; "toe" is not on the board.

212 Word Search IIWalkthrough · 1×

Example: the grid tea / ons and the words toe, tea, ten. The trie on the right follows the walk: a double ring is a word not found yet.

01201teaonsteoanerootfound—
free cell; a node not on the walkon the walk: a cell marked #, its nodecurrent callneighbour the walk goes on toneighbour no word goes on toword found

Put "toe", "tea", "ten" into a trie, as on the card; each word is kept on its last node (double ring)

01/50
restart · back · play · step
Speed
1function findWords(board, words):
2 root = trie of words // word kept on its end node
3 found = []
4 for each cell (r, c) of board:
5 if board[r][c] in root.children:
6 dfs(r, c, root.children[board[r][c]])
7 return found
8function dfs(r, c, node):
9 if node.word is not none:
10 add node.word to found
11 node.word = none // never added twice
12 ch = board[r][c]
13 board[r][c] = '#'
14 for each neighbour (nr, nc) of (r, c):
15 if board[nr][nc] in node.children:
16 dfs(nr, nc, node.children[board[nr][nc]])
17 board[r][c] = ch
state
found
[]
r
–
c
–
node
–
ch
–
click a step to go back

← → step · space play/pause

Why it works

  1. The walk steps into a cell only when the trie has a child for its letter, so the path so far is always the start of some word. A path that is the start of no word stops at once.
  2. One walk serves every word at the same time: "ten" and "tea" share "te", which is walked once, and each word is found when the walk reaches the node that holds it.
  3. The # mark keeps one path from using a cell twice, and the unmark on the way back frees it for other paths. Clearing the word from its node keeps a word that two paths spell from being added twice.

Complexity

Time O(m·n · 4 · 3^(L−1)) in the worst case for an m×n grid and words of up to L letters: a walk starts from each cell, the first step has 4 directions and every later one at most 3. The trie usually cuts this short. Memory O(total letters of the words) for the trie and O(L) for the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.