In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.
Return the sentence after the replacement.
Example 1:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"
Example 2:
Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" Output: "a a b c"
Constraints:
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i] consists of only lower-case letters.1 <= sentence.length <= 106sentence consists of only lower-case letters and spaces.sentence is in the range [1, 1000]sentence is in the range [1, 1000]sentence will be separated by exactly one space.sentence does not have leading or trailing spaces.Problem Overview: You receive a dictionary of root words and a sentence. Each word in the sentence should be replaced with the shortest dictionary root that is its prefix. If multiple roots match, the shortest one wins. If no root matches, keep the original word.
The core challenge is efficient prefix detection. For every word in the sentence, you need to determine whether any dictionary root is a prefix. Naively scanning the entire dictionary for every word works but wastes time when the dictionary grows large.
Approach 1: HashSet for Quick Prefix Search (Time: O(S * L), Space: O(D))
Store every root from the dictionary in a HashSet. Then process each word in the sentence one character at a time, building prefixes like w[0:1], w[0:2], w[0:3]. As soon as a prefix exists in the set, replace the word with that prefix. Stop immediately since the first match is the shortest root.
The key insight is constant-time hash lookups. Instead of checking each root against the word, you grow prefixes of the word and check membership in O(1). Limiting checks to the maximum root length avoids unnecessary work. This approach is simple and performs well for moderate dictionary sizes using a hash table combined with string prefix checks.
Approach 2: Trie for Prefix Search (Time: O(S), Space: O(D * L))
Insert every dictionary root into a Trie. Each node represents a character, and a flag marks the end of a root. When processing a sentence word, traverse the Trie character by character. If you hit a node marked as a root ending, you immediately return that prefix. If traversal breaks because the next character does not exist, the word has no valid root replacement.
The Trie structure naturally models prefix relationships. Instead of generating prefixes manually, you follow edges in the tree. Each character is visited once, which gives near linear time relative to the total number of characters in the sentence. This method is the most scalable solution when the dictionary contains many overlapping prefixes and is a classic application of a Trie data structure.
Recommended for interviews: The Trie approach is typically expected in interviews because it demonstrates knowledge of prefix data structures and achieves optimal lookup performance. The HashSet method is still valuable to mention first since it shows you recognize a simpler solution using standard library structures. Showing both approaches proves you understand the tradeoff between implementation complexity and algorithmic efficiency.
Store all roots in a HashSet. This allows for O(1) average time complexity when checking if a root exists. For each word in the sentence, check each prefix to determine if it is a root. As soon as you find a root, replace the word with this root.
This solution creates a set from the given dictionary containing root words. It then splits the sentence into words and attempts to replace each word with its shortest root using the replace() function. For each word, the function checks successive prefixes and returns the prefix (root) if it exists in the set. The replaced words are then joined back into a sentence and returned.
Python
JavaScript
Time Complexity: O(N * M), where N is the number of words in the sentence and M is the length of the longest word.
Space Complexity: O(D), where D is the total length of all the roots.
Build a Trie from the given dictionary of roots. A Trie is a tree-like data structure that holds a dynamic set of strings where all keys share a common prefix. For each word in the sentence, traverse through the Trie to find the shortest prefix that matches a segment of the word, if such a prefix exists, it replaces the word.
The Java solution involves constructing a Trie from the root words. Each word in the sentence is processed by traversing the Trie to find matching roots. If no root is found, the original word is used.
Time Complexity: O(D + N * K), D is the sum of lengths of all roots, N is the number of words, K is the length of the longest word.
Space Complexity: O(D), for storing the Trie.
We can use a trie to store all the roots in the dictionary. Define the trie node class Trie, which contains an array children of length 26 to store child nodes, and a boolean variable is_end to mark whether it is a complete root.
For each root, we insert it into the trie. For each word in the sentence, we search for its shortest root in the trie. If found, we replace the word; otherwise, we keep it unchanged.
The time complexity is O(n times |w| + L), and the space complexity is O(n times |w|), where n and |w| are the number of roots in the dictionary and the average length, respectively, and L is the total length of words in the sentence.
| Approach | Complexity |
|---|---|
| Using HashSet for Quick Search | Time Complexity: O(N * M), where N is the number of words in the sentence and M is the length of the longest word. |
| Using Trie for Prefix Search | Time Complexity: O(D + N * K), D is the sum of lengths of all roots, N is the number of words, K is the length of the longest word. |
| Trie | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Prefix Search | O(S * L) | O(D) | Good for simple implementation when dictionary size is moderate |
| Trie Prefix Search | O(S) | O(D * L) | Best for large dictionaries or heavy prefix matching workloads |
Replace Words | Using HashSet | Uber | Leetcode 648 | codestorywithMIK • codestorywithMIK • 9,032 views views
Watch 9 more video solutions →Practice Replace Words with our built-in code editor and test cases.
Practice on FleetCode