Tries
3 questions — the smallest section in the 150, and the one with the clearest payoff. All three are the same structure; the difference is what you ask it.
The one idea
A trie stores characters on edges, so every path from the root spells a prefix and words sharing a prefix share the path.
Why not just a hash set?
This is the question to have an answer for, because a HashSet ties a trie on exact lookup — hashing also reads the whole string, so both are O(L).
Hashing deliberately scatters related strings: "app" and "apple" land in unrelated buckets. So a set can only answer "is this exact string present?". A trie keeps prefixes as shared structure, so it can also answer:
| Query | HashSet | Trie |
|---|---|---|
| Exact word | O(L) | O(L) — tie |
| Any word with prefix P? | O(n · L) | O(L) |
| All words with prefix P | O(n · L) | O(L + output) |
| Wildcard match | O(n · L) | O(26^d · L), pruned |
| Is this path dead for ALL words? | impossible | O(1) |
The last row is why tries exist. Being able to refute an entire dictionary in one array lookup is what makes question 3 tractable — and it's something hashing cannot offer at any price.
isEnd is not optional
Insert "apple" and the path for "app" exists — but "app" was never a word. Reaching a node proves the string is a prefix; the flag proves it's a word.
search(w) → walk, then return node.isEnd
startsWith(p) → walk, then return node != nullTwo methods, one traversal, one line of difference. Verified: dropping the flag makes search("app") return true after inserting only "apple".
The escalation to Word Search II
Running Word Search I once per word repeats almost everything — every word starting with o re-explores the same cells. Putting the words in a trie inverts the loop: walk the board once, stepping the trie in lockstep, and a missing child prunes all k words at once.
O(k · m · n · 4^L) → O(k·L) build + O(m · n · 4^L) search.
The traps
| Trap | Symptom |
|---|---|
No isEnd flag (Q1) | A prefix reports as a stored word |
Returning true at the base case (Q2) | search("b.") matches "bad" |
Treating . as "zero or more" (Q2) | search("bad.") wrongly matches "bad" |
substring inside the DFS (Q2) | O(L) copy per level turns O(L) into O(L²) |
Indexing with '#' - 'a' (Q3) | Negative index — check the visited marker first |
| Not nulling the word after collecting (Q3) | Duplicates whenever a word has two paths |
Forgetting to restore board[r][c] (Q3) | Cells stay marked; later searches silently fail |
Space is the real cost
new Node[26] at every node means a node with one child still holds 26 references. For a sparse trie that's mostly waste. The alternatives:
Map<Character, Node>— allocates only real children; mandatory for a large alphabet, slower per step- Radix tree — collapses single-child chains into one node holding a substring
- DAWG — merges identical suffixes as well as prefixes
Verification
Every snippet compiled and cross-checked against an independent implementation — 1,100+ randomized cases:
- Q1 against a
HashSet(exact) plus a linear prefix scan, over 400 dictionaries × 30 probes - Q2 against a scan-every-word matcher, over 400 dictionaries × 40 wildcard patterns
- Q3 against Word Search I run once per word, over 300 random boards — and the board verified byte-for-byte restored afterwards
Two deliberately-broken variants confirm the traps are real:
- dropping
isEndmakessearch("app")returntrueafter inserting only"apple" - not nulling the collected word produced duplicate output on 172 of 300 random boards