Word Search II

hard

Find all words in a board using trie-guided DFS

Word Search II

Key Insight

Prune DFS on board cells by checking whether the current path exists as trie prefix.

Step 1Build Word Trie
Array
oath
0
pea
1
eat
2
rain
3
HashMap
o:1
p:1
e:1
r:1

Insert oath, pea, eat, and rain before DFS.

1 / 3

Learn the Pattern

Hash MapUse a hash map for O(1) lookup to track seen elements, frequencies, or complement values during array traversal.
Practice the Code

Step-by-Step Walkthrough: Word Search II

Prune DFS on board cells by checking whether the current path exists as trie prefix.

  1. Build Word Trie

    Insert oath, pea, eat, and rain before DFS.

  2. Start DFS with Prefix

    Cell "o" is valid start because trie has that edge.

  3. Emit Found Word

    When prefix hits a word node, record result and backtrack to explore remaining paths.