DSA Tracker

Visualize

Word Search II (Trie)

One shared trie, one board DFS, chasing every word at once

time O(m * n * 4^L)space O(sum of word lengths)

Searching the board once per word re-walks shared prefixes over and over. Inserting every word into one trie fixes that: a trie node's id is the prefix it spells, so words that start the same way share the same nodes. From any board cell, look up whether the trie node the DFS is currently at has a child for that letter. If it does, step into both the trie and the board together in one recursive call; if it does not, that branch can never spell a word, so stop immediately instead of exploring it. A trie node with `end` true is reported once and its word cleared, so a second board path to the same node can never report it twice.

Details

Animated on: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]. Answer: ["oath", "eat"].

Problem:Word Search II (Trie)Hard

One shared trie, one board DFS, chasing every word at once

step 1 / 11

h
t
a
o
a
e
p
t
a
e
n
i
a
r
•

Insert "oath", "pea", "eat", "rain" into one shared trie before touching the board. Shared prefixes share nodes: "oath" and "eat" both need an 'a' after their first letter, but that letter is a different trie node here because their first letters differ. Then scan every cell of the 4x4 board; a cell only starts a search when the trie's root has a child for that letter.

Pseudocode
1FUNCTION findWords(board, words)
2  trie <- BUILD TRIE FROM words
3  FOR EACH cell (r, c) ON board
4    dfs(r, c, trie.root, path <- EMPTY)
5  FUNCTION dfs(r, c, node, path)
6    IF node.children DOES NOT CONTAIN board[r][c]: RETURN
7    node <- node.children[board[r][c]]
8    APPEND board[r][c] TO path
9    IF node.end = TRUE: ADD node.word TO found; node.end <- FALSE
10    FOR EACH unvisited neighbour (nr, nc)
11      dfs(nr, nc, node, path)
12    REMOVE LAST FROM path
13  RETURN found

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Insert "oath", "pea", "eat", "rain" into one shared trie before touching the board. Shared prefixes share nodes: "oath" and "eat" both need an 'a' after their first letter, but that letter is a different trie node here because their first letters differ. Then scan every cell of the 4x4 board; a cell only starts a search when the trie's root has a child for that letter.
  2. board[0][0] = 'o' matches a child of the current trie node, so the DFS steps into trie node "o" and board cell (0, 0) together. (0, 0) is marked visited so this cell cannot be reused later on this word.
  3. board[0][1] = 'a' matches a child of the current trie node, so the DFS steps into trie node "oa" and board cell (0, 1) together. (0, 1) is marked visited so this cell cannot be reused later on this word.
  4. board[1][1] = 't' matches a child of the current trie node, so the DFS steps into trie node "oat" and board cell (1, 1) together. (1, 1) is marked visited so this cell cannot be reused later on this word.
  5. Trie node "oath" has word set, so path "oath" completes a full word: "oath" is added to the answer. Its word field is cleared so a second board path to the same node can never report it again.
  6. board[1][3] = 'e' matches a child of the current trie node, so the DFS steps into trie node "e" and board cell (1, 3) together. (1, 3) is marked visited so this cell cannot be reused later on this word.
  7. board[1][2] = 'a' matches a child of the current trie node, so the DFS steps into trie node "ea" and board cell (1, 2) together. (1, 2) is marked visited so this cell cannot be reused later on this word.
  8. Trie node "eat" has word set, so path "eat" completes a full word: "eat" is added to the answer. Its word field is cleared so a second board path to the same node can never report it again.
  9. board[2][3] = 'r' matches a child of the current trie node, so the DFS steps into trie node "r" and board cell (2, 3) together. (2, 3) is marked visited so this cell cannot be reused later on this word.
  10. From board (2, 3) none of the 4 neighbours hold a letter trie node "r" still needs, so this branch is a dead end. Backtrack: unmark (2, 3) and pop the call.
  11. Scan complete: ["oath", "eat"]. "pea" is never attempted at all — no board cell holds 'p', so trie node "p" never gets a matching start. "rain" enters trie node "r" once, at (2, 3), then dies immediately, exactly like the branch shown above.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Word Search II (Trie) in the editorAll Trie problemsBack to roadmap