Trie — Replace Words
↗ LeetCode: Replace Words · Medium · pattern chapter →
Given a dictionary of roots and a sentence, replace each word with its shortest root that is a prefix. If no root, keep the word.
Example 1 — dict=["cat","bat","rat"], sentence="the cattle was rattled by the battery" → "the cat was rat by the bat"
Constraints — dict ≤ 1000 roots; sentence words ≤ 1000. Brute checks every root against every word in O(n·L·m) — 10⁶·L (grows fast). Trie compresses shared prefixes: O(sum-of-lengths) build + O(L) per lookup = 10⁶ ops total.
Interview timer00:00
Approach 1 — HashSet + prefix scan
For each word, try prefixes of length 1..L; first match wins. O(word · L²) per word.
Approach 2 — Trie (canonical)
Insight. Insert all roots into a trie. For each word, walk the trie char-by-char; stop at first end node — that's the shortest prefix.
class Node { Node[] c = new Node[26]; String word; }
String replaceWords(List<String> dict, String sentence) {
Node root = new Node();
for (String r : dict) {
Node cur = root;
for (char ch : r.toCharArray()) {
int i = ch - 'a';
if (cur.c[i] == null) cur.c[i] = new Node();
cur = cur.c[i];
}
cur.word = r;
}
StringBuilder sb = new StringBuilder();
for (String w : sentence.split(" ")) {
if (sb.length() > 0) sb.append(' ');
Node cur = root;
String replacement = w;
for (char ch : w.toCharArray()) {
int i = ch - 'a';
if (cur.c[i] == null) break;
cur = cur.c[i];
if (cur.word != null) { replacement = cur.word; break; }
}
sb.append(replacement);
}
return sb.toString();
}Complexity — Time O(D + S) where D = total root chars, S = sentence chars; Space O(D).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| HashSet + prefix scan | O(S · L²) | O(D) | works but wasteful |
| Trie | O(D + S) | O(D) | canonical |
When to use which
- Many words, many prefix lookups → trie.
- Longest prefix instead → don't break early; track deepest
end. - "Any prefix in dict" → return boolean at first end.
Related problems
- Longest Word in Dictionary
- Implement Trie
- Word Break — DP with trie option