Replace Words
Understanding the Problem
We are given a list of "root" words and a sentence. For every word in the sentence, we need to check if any root is a prefix of that word. If so, we replace the word with the shortest such root. If no root is a prefix, the word stays as-is.
The shortest-root requirement matters. If the dictionary contains both "ca" and "cat", and we encounter "cattle," the answer is "ca" because it is shorter. We cannot stop at any matching root; we need the one with the smallest length.
So the problem reduces to: for each word, find the shortest prefix that exists in the dictionary. This is a prefix-matching problem, which is what hash sets and tries are good at.
Key Constraints:
dictionary.length <= 1000anddictionary[i].length <= 100-> The total characters across all roots is at most 100,000, so a Trie has at most that many nodes.sentence.length <= 10^6-> The sentence can be large, so we want per-word work that does not depend on dictionary size.Number of words <= 1000andword length <= 1000-> Per word, both a hash-set prefix scan and a Trie walk do at most 1000 steps.
Approach 1: Brute Force (Check All Roots)
Intuition
For each word in the sentence, loop through every root in the dictionary and check if that root is a prefix of the word. Among all matching roots, pick the shortest one. If no root matches, keep the word as-is.
This needs no extra data structures, only string comparison.
Algorithm
- Split the sentence into individual words.
- For each word, iterate through all roots in the dictionary.
- For each root, check if the word starts with that root.
- Track the shortest matching root. If a match is found and it is shorter than the current best, update the best.
- Replace the word with the shortest matching root (or keep the original if no root matched).
- Join all processed words back into a sentence with spaces.
Visualization and Code
Loading animation...
- Time Complexity: O(w d r). For each of the w words, we check all d roots. Each startsWith check takes O(r) time where r is the root length. In the worst case this is about 10^8 operations.
- Space Complexity: O(s). We store the split words and result string, proportional to the sentence length s.
This scans the entire dictionary for every word. The next approach instead generates each word's prefixes and looks them up in a set, stopping at the first match.
Approach 2: Hash Set with Prefix Checking
Intuition
Store all roots in a hash set for O(1) average lookup. Then for each word, generate its prefixes in increasing length order: length 1, length 2, length 3, and so on. The first prefix found in the set is the shortest matching root, so we stop there.
The word length k is at most 1000, so a word produces at most k prefix lookups, independent of dictionary size.
Algorithm
- Add all roots from the dictionary into a hash set.
- Split the sentence into words.
- For each word, iterate through prefix lengths from 1 to the word's length.
- At each length, extract the prefix and check if it exists in the hash set.
- If found, replace the word with this prefix and stop checking longer prefixes.
- If no prefix matches, keep the original word.
- Join all words back with spaces.
Visualization and Code
Loading animation...
- Time Complexity: O(w k^2). For each of the w words, we check prefixes of length 1 through k. Each substring creation is O(prefix length), so total work per word is O(k^2). Building the hash set is O(d r).
- Space Complexity: O(d * r + s). The hash set stores all roots. The split words and result take O(s) space.
The hash set approach allocates a substring object for every prefix it checks. A Trie removes that cost: it walks the word one character at a time along a path shared by all roots, testing every root at once.
Approach 3: Trie (Optimal)
Intuition
We build a Trie from all the roots in the dictionary. Then for each word in the sentence, we walk the Trie character by character. As soon as we reach a node marked as the end of a root, we have the shortest matching root. There is no substring allocation and no per-prefix hash computation.
One optimization applies during insertion: if we reach a node already marked as the end of a shorter root, we stop inserting the current root. Once "ca" is in the Trie, inserting "cat" past the "ca" node is wasted work, because a word starting with "cat" also starts with "ca", and "ca" is shorter, so "ca" is always the answer.
Walking a word from the Trie root downward visits its prefixes in increasing length order. The first end-of-root marker on that path is therefore the shortest root that is a prefix of the word, the answer the problem asks for.
The insertion optimization preserves this. If a shorter root S is a prefix of a longer root T, then for any word, matching S succeeds whenever matching T would, and S is shorter. So T can never be the chosen answer, and never inserting T past S's end marker removes only nodes that no search would ever reach.
Algorithm
- Build a Trie from all roots in the dictionary. Each node has up to 26 children (lowercase letters only) and a boolean flag indicating if it marks the end of a root.
- Split the sentence into words.
- For each word, traverse the Trie starting from the root node. For each character:
- If the current Trie node is marked as the end of a root, return the prefix up to this point.
- If the current character does not have a child in the Trie, stop. No root is a prefix.
- Otherwise, move to the child node and continue.
- If we exhaust the word without finding a root, keep the original word.
- Join all processed words with spaces.
Visualization and Code
Loading animation...
- Time Complexity: O(L + w * k). Building the Trie takes O(L) where L is the total length of all roots. For each of the w words, we walk the Trie for at most k characters. Early termination makes the average case much faster.
- Space Complexity: O(L * 26 + s). The Trie can have up to L nodes, each with 26 children pointers. Shared prefixes reduce this in practice. The result takes O(s) space.