Replace Words
MedPrompt
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 <= 106sentenceconsists of only lower-case letters and spaces.- The number of words in
sentenceis in the range[1, 1000] - The length of each word in
sentenceis in the range[1, 1000] - Every two consecutive words in
sentencewill be separated by exactly one space. sentencedoes not have leading or trailing spaces.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every prefix of each word in the sentence against a set of roots. We first store all the roots from the dictionary in a HashSet for quick lookups. Then, for each word in the sentence, we generate all its prefixes, from the shortest to the longest. The first prefix that we find in the HashSet is guaranteed to be the shortest root, so we use it as the replacement and move on to the next word.
Algorithm
- Create a
HashSetand add all roots from thedictionaryto it for O(1) average time lookups. - Split the
sentenceinto an array ofwords. - For each
wordin the sentence:- Iterate through all possible prefixes of the
word, from length 1 up to the word's full length. - For each
prefix, check if it exists in theHashSet. - The first prefix found will be the shortest root. Replace the word with this prefix and break the inner loop to proceed to the next word.
- If no prefix is found in the set, the original word is kept.
- Iterate through all possible prefixes of the
- Join the modified words back into a sentence.
Walkthrough
The core idea is to trade dictionary search time for prefix generation time. By putting all roots into a HashSet, we can check for the existence of a root in roughly constant time. However, to find the shortest root for a given word, we must check every single prefix of that word. We start with the prefix of length 1, check if it's in the set. If not, we check the prefix of length 2, and so on. The first time we find a prefix that is in the set, we know it must be the shortest possible root for that word, so we can stop and use it as the replacement. If we check all prefixes of a word and find no match, the word remains unchanged.
import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public String replaceWords(List<String> dictionary, String sentence) { Set<String> rootSet = new HashSet<>(dictionary); String[] words = sentence.split(" "); StringBuilder result = new StringBuilder(); for (int i = 0; i < words.length; i++) { String word = words[i]; String replacement = word; // Iterate through all prefixes of the word for (int j = 1; j <= word.length(); j++) { String prefix = word.substring(0, j); if (rootSet.contains(prefix)) { // Found the shortest root, no need to check longer prefixes replacement = prefix; break; } } result.append(replacement); if (i < words.length - 1) { result.append(" "); } } return result.toString(); }}Complexity
Time
O(S_R + L + N * W^2), where `S_R` is the total characters in the dictionary, `L` is the sentence length, `N` is the number of words, and `W` is the max word length. Building the set is `O(S_R)`. For each of `N` words, generating and checking all prefixes takes `O(W^2)` time, making this the dominant and slowest part.
Space
O(S_R + L), where `S_R` is the sum of the lengths of all roots in the dictionary (for the `HashSet`) and `L` is the length of the sentence (for storing the split words and the result).
Trade-offs
Pros
Conceptually simpler than a Trie.
Avoids iterating through the entire dictionary for each word.
Cons
Extremely inefficient due to the quadratic time complexity with respect to word length (
O(W^2)).This approach will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
This is a straightforward brute-force approach where for each word in the sentence, we iterate through the entire dictionary to find a matching root. To handle the requirement of using the shortest root, we simply keep track of the shortest valid root found so far for each word.
Algorithm
- Split the
sentenceinto an array ofwords. - Iterate through each
wordin thewordsarray. - For each
word, initialize areplacementvariable to be the word itself. - Start a nested loop to iterate through every
rootin thedictionary. - Inside the nested loop, check if the current
wordstarts with the currentroot. - If it does, and if this
rootis shorter than the currentreplacement, updatereplacementto thisroot. - After checking all roots, the
replacementvariable will hold the shortest possible root (or the original word). - Update the word in the array with the
replacement. - Finally, join the words in the array back into a single string.
Walkthrough
This method directly translates the problem statement into code. We first break the sentence down into its constituent words. Then, for every single word, we perform a linear scan through the entire dictionary. For each root in the dictionary, we check if our current word starts with it. If it does, we compare its length with the shortest root we've found so far for this word. If the new root is shorter, we update our choice. After checking all possible roots against a word, we replace the word with the shortest root we found. If no root was a prefix, the word remains unchanged as it was its own initial 'shortest root'.
import java.util.List; class Solution { public String replaceWords(List<String> dictionary, String sentence) { String[] words = sentence.split(" "); for (int i = 0; i < words.length; i++) { String word = words[i]; String shortestRoot = word; for (String root : dictionary) { if (word.startsWith(root)) { if (root.length() < shortestRoot.length()) { shortestRoot = root; } } } words[i] = shortestRoot; } return String.join(" ", words); }}Complexity
Time
O(L + N * D * R), where `L` is the sentence length, `N` is the number of words, `D` is the dictionary size, and `R` is the average root length. Splitting the sentence takes `O(L)`. The main work is in the nested loops, which run `N * D` times, with the `startsWith` check taking `O(R)` time.
Space
O(L), where `L` is the length of the sentence. This space is used to store the array of words and the final result string.
Trade-offs
Pros
Easy to understand and implement.
Requires minimal auxiliary space.
Cons
Very inefficient for large inputs due to the nested loops.
The time complexity
O(N * D * R)will be too high for the given constraints and will likely time out.
The most efficient way to solve this problem is by using a Trie (also known as a prefix tree). A Trie is a tree-like data structure perfect for problems involving prefixes. We first build a Trie by inserting all the roots from the dictionary. Then, for each word in the sentence, we traverse the Trie to find the shortest prefix of that word that corresponds to a root in the dictionary.
Algorithm
- Define a
TrieNodeclass containing an array for child nodes and a field to mark the end of a word (e.g., a string to store the root). - Build a Trie by inserting every
rootfrom thedictionary. - Split the
sentenceinto words. - For each
wordin the sentence:- Traverse the Trie from the root, character by character, following the path corresponding to the
word. - During traversal, if you reach a node that marks the end of a root, you have found the shortest possible root prefix. Record this root and break the traversal for the current word.
- If the path breaks (a character has no corresponding child node), it means no root matches this prefix. Stop and keep the original word.
- If you traverse all characters of the word without finding a root, keep the original word.
- Traverse the Trie from the root, character by character, following the path corresponding to the
- Replace the original word with the found root (if any).
- Join the processed words to form the final sentence.
Walkthrough
A Trie is tailor-made for prefix-based searches. We begin by constructing the Trie. Each node represents a character, and a path from the root to a node represents a prefix. We insert all dictionary roots into this Trie. We modify the Trie nodes to hold the actual root word at the node where the root terminates. This is a key optimization.
After building the Trie, we process the sentence. For each word, we walk down the Trie, following the path given by the word's characters. As we traverse, if we land on a node that contains a stored root word, we know we've found a valid prefix. Because we are processing the word from its beginning, the first such root we encounter is guaranteed to be the shortest one. We can immediately use this root as the replacement and move to the next word in the sentence. If our traversal is blocked (no child for a character) or finishes without finding a root, the word is not a derivative and is left as is.
import java.util.List; class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; String word = null; // Store the full word at the end node } public String replaceWords(List<String> dictionary, String sentence) { TrieNode root = new TrieNode(); // 1. Build the Trie with all roots for (String word : dictionary) { TrieNode curr = root; for (char c : word.toCharArray()) { if (curr.children[c - 'a'] == null) { curr.children[c - 'a'] = new TrieNode(); } curr = curr.children[c - 'a']; } curr.word = word; } String[] words = sentence.split(" "); StringBuilder result = new StringBuilder(); // 2. Replace words in the sentence by searching the Trie for (int i = 0; i < words.length; i++) { String word = words[i]; TrieNode curr = root; String replacement = word; // Default to original word for (char c : word.toCharArray()) { if (curr.children[c - 'a'] == null || curr.word != null) { // Path broken or a shorter root has already been found break; } curr = curr.children[c - 'a']; if (curr.word != null) { // Found a root prefix. It's the shortest one. replacement = curr.word; break; } } result.append(replacement); if (i < words.length - 1) { result.append(" "); } } return result.toString(); }}Complexity
Time
O(S_R + L), where `S_R` is the sum of all characters in the dictionary and `L` is the length of the sentence. Building the Trie takes `O(S_R)`. Processing the sentence takes `O(L)` because each character is visited once during the Trie traversal.
Space
O(S_R + L), where `S_R` is the sum of lengths of all roots (for the Trie) and `L` is the sentence length (for the split words and result).
Trade-offs
Pros
Highly efficient with linear time complexity relative to the total input size.
The optimal solution for this problem, easily handling the given constraints.
Cons
Requires implementing a custom Trie data structure, which adds complexity to the code compared to using built-in collections.
Solutions
Solution
class Trie { private Trie [] children = new Trie [ 26 ]; private int ref = - 1 ; public void insert ( String w , int i ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; } node . ref = i ; } public int search ( String w ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { return - 1 ; } node = node . children [ idx ]; if ( node . ref != - 1 ) { return node . ref ; } } return - 1 ; } } class Solution { public String replaceWords ( List < String > dictionary , String sentence ) { Trie trie = new Trie (); for ( int i = 0 ; i < dictionary . size (); ++ i ) { trie . insert ( dictionary . get ( i ), i ); } List < String > ans = new ArrayList <>(); for ( String w : sentence . split ( "\\s" )) { int idx = trie . search ( w ); ans . add ( idx == - 1 ? w : dictionary . get ( idx )); } return String . join ( " " , ans ); } }class Trie { private: Trie * children [ 26 ]; int ref ; public: Trie () : ref ( - 1 ) { memset ( children , 0 , sizeof ( children )); } void insert ( const string & w , int i ) { Trie * node = this ; for ( auto & c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) { node -> children [ idx ] = new Trie (); } node = node -> children [ idx ]; } node -> ref = i ; } int search ( const string & w ) { Trie * node = this ; for ( auto & c : w ) { int idx = c - 'a' ; if ( ! node -> children [ idx ]) { return - 1 ; } node = node -> children [ idx ]; if ( node -> ref != - 1 ) { return node -> ref ; } } return - 1 ; } }; class Solution { public: string replaceWords ( vector < string >& dictionary , string sentence ) { Trie * trie = new Trie (); for ( int i = 0 ; i < dictionary . size (); ++ i ) { trie -> insert ( dictionary [ i ], i ); } stringstream ss ( sentence ); string w ; string ans ; while ( ss >> w ) { int idx = trie -> search ( w ); ans += ( idx == - 1 ? w : dictionary [ idx ]) + " " ; } ans . pop_back (); return ans ; } };class Trie : def __init__ ( self ): self . children : List [ Trie | None ] = [ None ] * 26 self . ref : int = - 1 def insert ( self , w : str , i : int ): node = self for c in w : idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . ref = i def search ( self , w : str ) -> int : node = self for c in w : idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : return - 1 node = node . children [ idx ] if node . ref != - 1 : return node . ref return - 1 class Solution : def replaceWords ( self , dictionary : List [ str ], sentence : str ) -> str : trie = Trie () for i , w in enumerate ( dictionary ): trie . insert ( w , i ) ans = [] for w in sentence . split (): idx = trie . search ( w ) ans . append ( dictionary [ idx ] if idx != - 1 else w ) return " " . join ( ans )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.