Replace Words
Given a dictionary of root words and a sentence, replace every word in the sentence with its shortest root from the dictionary. If a word has no root, leave it unchanged.
- 1 <= dictionary.length <= 1000
- 1 <= dictionary[i].length <= 100
- dictionary[i] consists of only lower-case letters.
- 1 <= sentence.length <= 10⁶
- sentence consists of only lower-case letters and spaces.
- The number of words in sentence is in the range [1, 1000]
- The length of each word in sentence is in the range [1, 1000]
- Every two consecutive words in sentence will be separated by exactly one space.
- sentence does not have leading or trailing spaces.
Intuition
This is replace words leetcode problem 648: given a dictionary of roots and a sentence, replace every word with the shortest root that forms its prefix.
Checking each word against every root is O(words × roots × length) and repeats enormous amounts of prefix comparison. A trie removes that redundancy:
- Insert every root into a trie, then walk each word down it one character at a time, stopping at the first node marked as a root's end.
Stopping at the first marked node is what gives the shortest root automatically. If both "a" and "ab" are roots, the walk hits "a" first and returns it — no comparison of candidate lengths is needed anywhere.
That property is the reason a trie fits this problem so precisely.
The walk ends in one of three ways. A marked node means a root was found — return the prefix accumulated so far. Running out of characters, or reaching a point where the next character has no child, means no root matches and the original word is returned unchanged.
Forgetting that third case leaves words dropped from the output entirely.
A hash set of roots is a simpler alternative: for each word, test every prefix from shortest to longest and return the first match. That is O(wordLength²) per word for the substring construction, and fine when words are short — but the trie generalises better and is what the problem targets.
The sentence must be rebuilt with single spaces between words, preserving the original word order.
Building the trie is O(total root characters), and each word is processed in O(its length).
When you need to find the shortest or longest prefix of a string that belongs to a known set, a trie gives you the answer in a single walk. The pattern shows up whenever the problem says 'dictionary of roots', 'prefix matching', or 'replace by shortest match'. Hash sets can simulate this with a loop over prefix lengths, but the trie is the natural fit.
Approach
Before reading on: price up what the direct approach costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O(D + S) time and O(D) space.
Build a trie of roots
Insert every root, marking the node at each root's final character. This shares prefix comparisons across all roots rather than repeating them per word.
Walk each word down the trie
Follow one character at a time from the root node, accumulating the prefix travelled. The walk is bounded by the word's length.
Stop at the first marked node
The first root encountered is necessarily the shortest, so no length comparison is needed. This is why a trie fits the problem exactly.
Return the word unchanged when no root matches
If the characters run out or a child is missing, no root applies. Forgetting this case drops words from the output entirely.
Rebuild the sentence
Join the replaced words with single spaces, preserving the original order. Each word is handled independently of the others.
Cost of the approach
Building the trie is O(total root characters) and each word costs O(its length), giving O(R + W) overall with O(R) space.
Solution & live demo
Common pitfalls
Not stopping at the first (shortest) root
for ch in word:
node = node[ch]
if '#' in node:
root = longest_so_farfor ch in word:
node = node[ch]
if '#' in node:
return current_prefixContinuing past the first word-end flag finds longer roots instead of shorter ones. The problem asks for the shortest root, so you must stop at the first hit.
Forgetting to check for missing characters in the trie
for ch in word:
node = node[ch]for ch in word:
if ch not in node:
break
node = node[ch]If a character is not in the trie, the word has no root. Without the check you get a KeyError (dict) or NoneType error (object). The word should be kept as-is.
Splitting and rejoining without preserving single spaces
return ' '.join(sentence.split(' '))return ' '.join(sentence.split())
Using split(' ') on a sentence with multiple consecutive spaces creates empty strings in the list, which join preserves as extra spaces. split() handles any whitespace and produces clean tokens.
Edge cases
The trie walk falls off without hitting a word-end flag. The original word is kept unchanged — no special branch needed.
cat and word catThe trie walk reaches the end of the root and sees the word-end flag, so it replaces the word with itself. Functionally a no-op, correctly handled.
a and ap for word appleThe trie walk hits the shorter root a first and returns immediately. The longer root is never reached.