Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Build a Trie from the dictionary of roots. For each word in the sentence, walk the trie character-by-character and stop at the FIRST node marked as a word-end — that's the shortest matching root, which is the replacement. If you fall off the trie (a missing child) or never hit a word-end, keep the original word. Building the trie is O(total root chars); replacing each word is O(its length), so the whole thing is O(total characters) — far better than testing every word against every root.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reach for a trie to index many prefixes (instead of comparing every word against every root), and whether you correctly grab the SHORTEST root by stopping at the first word-end during the walk.
Where candidates slip
Comparing each sentence word against each root (O(words × roots × length) brute force), or matching the longest root instead of the shortest, or treating a missing child as a match and corrupting the output.
How to stand out
State that roots sharing prefixes scream 'trie', build it once, then explain that the first isEnd encountered during the descent is necessarily the shortest root — so a single early-terminating walk per word solves it in linear time.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewReplace each word with its shortest root prefixMany roots sharing prefixes?No, very few rootsYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
HashSet of Roots — Probe Each Prefix
1Hint 1Explore hintHide hint
If you put every root in a hash set, how would you find the shortest root that prefixes a given word?
2Hint 2Explore hintHide hint
For each word, try its prefixes from shortest to longest: word[0:1], word[0:2], … and check each against the set. The first hit is the shortest root.
3Hint 3Explore hintHide hint
Cap the prefix length at the longest root so you don't probe forever; if no prefix is in the set, keep the original word.
A · Core idea
Store all roots in a hash set, then for each sentence word generate its prefixes in increasing length and look each up. The first prefix found in the set is, by construction, the shortest root that prefixes the word.
Why probe shortest-to-longest. The problem wants the shortest matching root, so testing word[0:1], then word[0:2], and so on means the very first set hit is the answer — you stop immediately and never consider longer roots. Probing longest-first would force you to keep a running minimum and do more work.
Why cap the prefix length. A word can be far longer than any root, so probing every prefix up to the word's full length wastes time on prefixes that can't possibly be a root. Bounding the probe at the maximum root length keeps the inner loop tight.
Why string slicing makes this quadratic-ish. Each prefix word[0:k] is a fresh string of length k that must be built and hashed, so summing k = 1..L gives O(L²) work per word in the worst case. For a single 10⁶-character sentence split into ≤1000 words this is usually fine, but it's strictly more work than a trie, which reads each character once.
Why it's still worth mentioning. With only a handful of roots and no shared prefixes, this approach is shorter to write and has no node-allocation overhead. State it as the simple option, note its cost, then upgrade to the trie when the dictionary is large or prefix-heavy.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
dictionary = ["cat"], word = "cattle"k=1
"c" in set? no
continue"cat"C · Code with teaching comments
Reference implementation previewpublic String replaceWords(List<String> dictionary, String sentence) { Set<String> roots = new HashSet<>(dictionary); int maxLen = 0; for (String r : dictionary) maxLen = Math.max(maxLen, r.length()); Explore the full codeHide the full code
D · Why it works and complexityO(total sentence chars × max root length) timeO(total root chars) spaceOpen the invariant and proofExplore the proofHide the proof
The hash set can only answer 'is this exact string a root?', so you must manufacture every candidate prefix and test it. The trie flips that: it walks the word's characters once and the roots reveal themselves as isEnd nodes along the path — no prefix strings are ever materialized.
ComplexityO(total sentence chars × max root length) time, O(total root chars) space — For each word you build and hash up to L prefixes, and hashing a length-k prefix costs O(k); summed it's roughly O(L²) per word, or O(L × maxRootLen) if you cap at the longest root. Across the sentence that's O(total chars × maxRootLen). The set stores O(total root chars).
E · Edge cases and pitfalls6word with no root prefix — Inner loop never matches → replacement stays the original word.Explore edge casesHide edge cases
Edge cases handled
word with no root prefixInner loop never matches → replacement stays the original word.empty dictionarymaxLen = 0, inner loop never runs → every word kept unchanged.root longer than the wordlimit caps at word length, so an over-long root can't match — correct, since it can't be a prefix.
Pitfalls
- Probing longest-first and forgetting to track the minimum — returns a longer root than required.
- Not capping the prefix length at maxLen — wasted probes on impossibly long prefixes.
- Using `roots.contains(word)` only (exact match) — misses the case where a shorter root prefixes the word.
Approach 2 of 2 · Optimal
Trie of Roots — Stop at First isEnd (Optimal)
1Hint 1Explore hintHide hint
The roots share prefixes (cat, cattle, car all start with 'ca'). What structure stores shared prefixes once and lets you walk a word character-by-character?
2Hint 2Explore hintHide hint
Insert every root into a trie, marking isEnd on each root's final node. Then for each word, descend the trie one character at a time.
3Hint 3Explore hintHide hint
The moment you reach a node with isEnd = true, you've spelled out a complete root — and because you're walking from the start, it's the SHORTEST such root. Replace and stop. If a child is missing, keep the original word.
A · Core idea
Index the dictionary as a trie — a tree whose edges are characters and whose nodes flag where a root ends — then let each sentence word walk down it. The first isEnd node the walk passes spells the shortest root that prefixes the word.
Why a trie is the right index. Roots like cat, cattle, and car share the prefix ca. A trie stores that shared path once and branches only where the roots differ, so a single descent simultaneously checks the word against all roots that could prefix it. The hash set, by contrast, had to manufacture and test each candidate prefix separately.
Why the first isEnd is the shortest root. We descend from the root following the word's characters in order, so node depth equals prefix length. Word-ends appear in increasing depth as we go deeper. The instant we hit one, we've found a complete root, and since we've examined every shorter prefix already (and none was a word-end), this is by definition the shortest matching root. Stopping there is exactly the 'shortest root wins' rule — no comparison or min-tracking needed.
Why a missing child means 'keep the word'. If at some character the current node has no matching child, then no root continues along this path — and since we hadn't yet hit an isEnd, no root is a prefix of the word at all. We break out and emit the original word untouched. The same logic covers the case where we consume the whole word without ever passing an isEnd.
Why building once pays off. The trie is constructed a single time from the dictionary, then reused for every word in the sentence. With up to 1000 words against a 1000-root dictionary, amortizing the build across all queries is what turns a potential O(words × roots × length) brute force into linear time over the total input size.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
dictionary = ["cat","bat","rat"], word = "cattle"Interactive diagram
Trie of roots cat / bat / rat
build trieWalking 'cattle' follows c→a→t and stops at t (isEnd) — the shortest root 'cat'. Double-circle nodes are word-ends.
"cat"C · Code with teaching comments
D · Why it works and complexityO(total root chars + total sentence chars) timeO(total root chars) spaceOpen the invariant and proofExplore the proofHide the proof
This is Implement Trie with one twist: instead of querying for an exact word (walk to the end, check isEnd) or a prefix's existence (walk, check the node exists), you query for the earliest word-end along the path. The children-map + isEnd skeleton is identical — only the stopping condition changes. Recognizing that 'shortest prefix in a set' = 'first isEnd on a trie walk' is the whole insight.
ComplexityO(total root chars + total sentence chars) time, O(total root chars) space — Building the trie inserts every root character exactly once → O(sum of root lengths). Replacing scans each sentence character at most once during its word's walk, with O(1) child lookups → O(sum of sentence lengths). No re-hashing of prefix substrings, so it strictly dominates the hash-set probing.
E · Edge cases and pitfalls6roots ["catt","cat"], word "cattle" — Walk hits cat's isEnd at depth 3 before reaching catt — returns the shorter "cat".Explore edge casesHide edge cases
Edge cases handled
roots ["catt","cat"], word "cattle"Walk hits cat's isEnd at depth 3 before reaching catt — returns the shorter "cat".word "the" with no matching root't' may exist but no isEnd is reached, or 't' child is missing → returns "the" unchanged.single-letter root "a", word "apple"First step reaches 'a' with isEnd → returns "a" immediately.
Pitfalls
- Continuing the walk past the first isEnd to find a longer root — the problem wants the shortest.
- Creating child nodes during the query walk (copying insert logic) — corrupts the trie; the lookup must be read-only.
- Returning an empty/garbage string when no root matches instead of the original word.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewclass Solution { private static class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd = false; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Matching the longest root instead of the shortest
If you keep descending after the first isEnd to find a deeper word-end, you return a longer root. The problem requires the shortest, so you must stop at the first isEnd.
Explore the code comparisonHide the code comparison
Matching the longest root instead of the shortest
If you keep descending after the first isEnd to find a deeper word-end, you return a longer root. The problem requires the shortest, so you must stop at the first isEnd.
Don't write this
best = word
for ... walking the trie ...:
if node.is_end:
best = ''.join(prefix) # keeps overwriting → ends on the LONGEST root
return bestWrite this instead
for ... walking the trie ...:
if node.is_end:
return ''.join(prefix) # stop at the FIRST (shortest) root
return word2Mutating the trie during lookup
Reusing insert's 'create child if missing' inside the query walk silently inserts the query word as a root, so later words get wrongly replaced. The lookup must bail out, never create.
Explore the code comparisonHide the code comparison
Mutating the trie during lookup
Reusing insert's 'create child if missing' inside the query walk silently inserts the query word as a root, so later words get wrongly replaced. The lookup must bail out, never create.
Don't write this
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) {
node.children[i] = new TrieNode(); // side effect — corrupts the trie
}
node = node.children[i];
}Write this instead
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) {
return word; // read-only: no root here, keep the word
}
node = node.children[i];
if (node.isEnd) return prefix.toString();
}Revise
Carry the pattern into the interview
Pattern to remember
Trie of roots + shortest-prefix lookup per word
Code pattern to memorize
insert each root into a trie, mark isEnd on its last node
for each word in sentence:
node = root; prefix = ""
for ch in word:
if ch not in node.children: break # no root prefixes this word
prefix += ch
node = node.children[ch]
if node.isEnd: replace with prefix; stop # SHORTEST root wins
else: keep the original wordRules to remember
- 1Stop at the first isEnd while walking — that yields the SHORTEST root, which the problem requires (
catbeatscattle). - 2If a child is missing mid-walk, no root is a prefix → keep the original word unchanged.
- 3If you finish the word without hitting isEnd, again keep the original word — a root must be a prefix, not a suffix or substring.
- 4Build the trie once up front; then each sentence word is an independent O(L) lookup.
- 5Track the matched prefix as you descend (or remember the depth) so you can emit it directly without re-slicing.
- 6Roots replace words only as a prefix from index 0 — never a match in the middle of the word.
Use this pattern when
- You must match each query string against a SET of prefixes/roots efficiently
- Many candidate prefixes share common beginnings (classic trie territory)
- You need the SHORTEST (or longest) matching prefix, not just any membership
- Dictionary is fixed and reused across many queries → amortize one trie build
Choose another pattern when
- Only one or two roots → a couple of `startsWith` checks beat building a trie
- Matches can occur anywhere in the word, not as a leading prefix → this isn't a prefix problem
- You need fuzzy / wildcard matching → that's a DFS-over-trie variant (Add and Search Words)
- Roots don't share prefixes and the set is tiny → a HashSet of roots with length-bounded probing is simpler
Interview takeaway
Replace Words is the trie's bread-and-butter: index a set of roots so each word finds its shortest prefix in O(L). The 'stop at the first isEnd' tweak is the entire problem — it's the same children-map + isEnd skeleton as Implement Trie, just queried for the earliest word-end instead of the exact one. Once you see roots-as-a-trie, autocomplete and dictionary problems all collapse to this shape.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTrie as a prefix index. Insert the roots once, then each word's shortest matching root is the first isEnd encountered on a single O(L) descent. Same children-map + isEnd skeleton as Implement Trie, queried for the earliest word-end. The trie-of-a-word-set idea powers Word Search II and autocomplete.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Implement Trie (Prefix Tree)The foundation — children map + isEnd. Replace Words layers a 'first isEnd' query on this skeleton.
- Design Add and Search Words Data StructureAdds '.' wildcards — the walk becomes a DFS that branches over all children on a dot.
- Word Search IIBuild a trie of words, then DFS the grid, pruning paths that fall off the trie.
- Longest Word in DictionaryComing soonTrie where a word is buildable only if every prefix is also a word — DFS only through isEnd nodes.