Replace Words
Swap each word for its shortest root — the prefix question a hash map has to brute-force and a trie answers in one walk
Problem Statement
Given a dictionary of roots and a sentence, replace every word that has a root as its prefix with that root. If several roots match, use the shortest.
Input: dictionary = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Input: dictionary = ["a", "b", "c"]
sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"Intuition
The brute force: for each word, test every root to see whether it is a prefix, keeping the shortest match.
"cattle" vs ["cat", "bat", "rat"]
does it start with "cat"? yes → candidate, length 3
does it start with "bat"? no
does it start with "rat"? noThat is O(words × roots × length). With a large dictionary the roots loop dominates, and almost every test fails immediately on the first character — wasted work repeated for every word.
The insight
Put the roots in a trie, then walk each word down it one character at a time.
The moment you land on a node marked as the end of a root, you have found a match — and because you walked from the shortest prefix outward, it is automatically the shortest one. Stop there.
If the path breaks before any root is found, no root matches. Keep the word.
Two things fall out for free:
Shortest is automatic. Walking c → a → t reaches "cat" before it could ever reach "cattle". Depth is length, so the first hit is the shortest. No comparison, no tracking a minimum.
Failure is early. A word starting with z fails at the first character, having consulted the whole dictionary at once — instead of testing every root separately.
Approach
Insert every root into a trie
Mark the last node of each root as a word end.
For each word in the sentence, walk it down the trie
Character by character from the root.
Stop at the first end-of-root node
Return the characters consumed so far. This is the shortest matching root.
If the path breaks, keep the original word
A missing child means no root is a prefix of this word.
[]Solution
class TrieNode:
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_root = False
def replace_words(dictionary: list[str], sentence: str) -> str:
"""Replace each word with its shortest matching root."""
trie = TrieNode()
for root in dictionary:
node = trie
for char in root:
node = node.children.setdefault(char, TrieNode())
node.is_root = True
def shortest_root(word: str) -> str:
node = trie
for i, char in enumerate(word):
if char not in node.children:
return word # no root is a prefix
node = node.children[char]
if node.is_root:
return word[: i + 1] # first hit is the shortest
return word
return " ".join(shortest_root(w) for w in sentence.split())setdefault creates the child only when missing and returns it either way — the insert loop in one line.
Why returning on the first hit gives the shortest root
The walk goes one character deeper per step, so it encounters prefixes in increasing length order: "c", then "ca", then "cat".
If both "cat" and "cattle" were roots, "cat" is reached first — it is nearer the root of the trie. Returning immediately is therefore not just an optimisation; it is the "shortest" requirement, implemented by the structure rather than by comparison.
Complexity Analysis
Time Complexity
O(D + S)
Space Complexity
O(D)
Time — D is the total characters across all roots (building the trie), S the total characters in the sentence (walking it). Compare the brute force at O(words × roots × length).
Space — the trie, bounded by the total characters in the dictionary and smaller when roots share prefixes.
Edge Cases
Related Problems
- Implement Trie — building the structure this relies on
- Word Break — another dictionary problem where a trie can replace repeated hashing
- Longest Common Prefix — prefixes without needing a trie