DSA Tracker

Visualize

Word Search II

One 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 - 'oath' and 'oat' would retrace the same first three cells. Building one Trie out of all the words fixes that: from any board cell, look up whether the current Trie node has a child for that letter. If it does, step into both the Trie and the board together and keep going in 4 directions; if it does not, that branch can never spell a word, so stop immediately. A Trie node with a completed word is reported once and then cleared, so revisiting the same letters later 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 IIHard

Pattern:Trie

One Trie, one board DFS, chasing every word at once

step 1 / 14

Build one Trie from "oath", "pea", "eat", "rain", then scan every cell of the 4x4 board. Whenever a cell's letter matches a Trie child of the current node, step into the Trie and the board together — this lets one DFS chase all 4 words at once instead of re-scanning the board per word.

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.word != NULL: ADD node.word TO found; node.word <- NULL
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 14 steps
  1. Build one Trie from "oath", "pea", "eat", "rain", then scan every cell of the 4x4 board. Whenever a cell's letter matches a Trie child of the current node, step into the Trie and the board together — this lets one DFS chase all 4 words at once instead of re-scanning the board per word.
  2. board[0][0] = 'o' matches the Trie child at this depth, so the search descends: path is now "o". (0, 0) is marked visited so this cell cannot be reused later in the same word.
  3. board[0][1] = 'a' matches the Trie child at this depth, so the search descends: path is now "oa". (0, 1) is marked visited so this cell cannot be reused later in the same word.
  4. board[1][1] = 't' matches the Trie child at this depth, so the search descends: path is now "oat". (1, 1) is marked visited so this cell cannot be reused later in the same word.
  5. board[2][1] = 'h' completes a Trie word: path "oath" matches "oath" exactly, so it is added to the answer. The word is cleared from the Trie node so a second path to the same letters can never report it again.
  6. Path unwinds all the way back to "" as the recursion returns to the top-level scan.
  7. board[1][3] = 'e' matches the Trie child at this depth, so the search descends: path is now "e". (1, 3) is marked visited so this cell cannot be reused later in the same word.
  8. board[1][2] = 'a' matches the Trie child at this depth, so the search descends: path is now "ea". (1, 2) is marked visited so this cell cannot be reused later in the same word.
  9. board[1][1] = 't' completes a Trie word: path "eat" matches "eat" exactly, so it is added to the answer. The word is cleared from the Trie node so a second path to the same letters can never report it again.
  10. Path unwinds all the way back to "" as the recursion returns to the top-level scan.
  11. board[2][3] = 'r' matches the Trie child at this depth, so the search descends: path is now "r". (2, 3) is marked visited so this cell cannot be reused later in the same word.
  12. From (2, 3) none of the 4 neighbours hold a letter the Trie still needs after "r", so this branch is a dead end. Backtrack: unmark (2, 3) and pop 'r' from the path.
  13. Path unwinds all the way back to "" as the recursion returns to the top-level scan.
  14. Scan complete: ["oath", "eat"]. "pea" is never even attempted — no board cell holds 'p', so the Trie's 'p' child never gets a matching start. "rain" starts once, at (2, 3), and dies on its first step, as shown above.

Now solve it yourself

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

Solve Word Search II in the editorAll Backtracking problemsBack to roadmap