grid47 Exploring patterns and algorithms
Sep 3, 2024
8 min read
Solution to LeetCode 648: Replace Words Problem
In English, certain words can be formed by adding a suffix to a root word. Given a list of root words and a sentence, replace every word in the sentence that is a derivative of any root word with the shortest root. If a word can be formed by more than one root, replace it with the shortest root.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of root words (dictionary) and a sentence, both represented as strings.
Example: dictionary = ["dog", "cat", "rat"], sentence = "the dogs were caught by the rats"
Constraints:
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lowercase letters.
• 1 <= sentence.length <= 10^6
• sentence consists of only lowercase letters and spaces.
• The number of words in sentence is in the range [1, 1000].
• Each word in sentence has a length in the range [1, 1000].
• There are no leading or trailing spaces in the sentence.
Output: The output should be a sentence with all derivative words replaced by the shortest corresponding root word.
Example: the dog were caught by the rat
Constraints:
• The output will be a string with words separated by spaces, and no leading or trailing spaces.
Goal: Replace each word in the sentence with the shortest root word it can be derived from.
Steps:
• 1. Build a Trie data structure to store all root words.
• 2. For each word in the sentence, attempt to find the shortest prefix that exists in the Trie.
• 3. Replace the word with its root if a match is found.
Goal: The input and output should be handled efficiently due to the large size constraints.
Steps:
• The solution must handle up to 1000 root words and a sentence of length up to 10^6 efficiently.
Assumptions:
• The dictionary is non-empty.
• The sentence contains words that are potentially derivatives of roots.
• Input: dictionary = ["dog", "cat", "rat"], sentence = "the dogs were caught by the rats"
• Explanation: The words 'dogs' and 'rats' are derivatives of 'dog' and 'rat' respectively, so they are replaced with these shorter roots.
Approach: We use a Trie data structure to efficiently store and check the prefixes of words in the sentence to replace them with the shortest root.
Observations:
• Trie is a good choice because it allows efficient prefix matching.
• We need to handle the large input efficiently by ensuring that the lookup and insertion in the Trie are fast.
Steps:
• 1. Create a TrieNode structure to store child nodes and mark the end of a word.
• 2. Insert all the root words into the Trie.
• 3. For each word in the sentence, check if it has a prefix in the Trie and replace it with the shortest matching root.
Empty Inputs:
• The sentence is guaranteed to have at least one word.
Large Inputs:
• Handle cases where the sentence is large (up to 10^6 characters).
Special Values:
• Consider cases where no words in the sentence are derivatives of the roots.
Constraints:
• Ensure that the solution efficiently handles the large input constraints.
classSolution {
TrieNode* root;
public:void insert(string w) {
TrieNode* st = root;
for(charc: w) {
if(!st->child[c -'a']) st->child[c -'a'] =new TrieNode();
st = st->child[c -'a'];
}
st->isEnd =true;
}
string check(string w) {
TrieNode* st = root;
string s ="";
for(charc: w) {
if(st->child[c -'a']) st = st->child[c -'a'];
elsebreak;
s += c;
if(st->isEnd) return s;
}
return w;
}
string replaceWords(vector<string>& dictionary, string sentence) {
root =new TrieNode();
for(autow: dictionary) insert(w);
istringstream ss(sentence);
string word ="", ans ="";
for(; ss>>word;) {
ans += check(word);
ans +=' ';
}
ans.pop_back();
return ans;
}
1 : Class Definition
classSolution {
The class `Solution` is defined, which will contain methods for inserting words into a trie and checking and replacing words in a sentence.
2 : Trie Node Initialization
TrieNode* root;
A pointer `root` is declared that will point to the root of the trie structure used to store words.
3 : Access Modifier
public:
The `public` access modifier allows the methods `insert`, `check`, and `replaceWords` to be accessible from outside the class.
4 : Method Definition
voidinsert(string w) {
The `insert` method is defined to insert a word into the trie.
5 : Trie Node Traversal
TrieNode* st = root;
A temporary pointer `st` is initialized to the root of the trie. This pointer will be used to traverse the trie as we insert characters of the word.
6 : Character Insertion
for(charc: w) {
This loop iterates over each character in the word `w` to insert it into the trie.
The `replaceWords` method is defined to replace words in a sentence based on the dictionary, using the trie structure.
20 : Initialize Trie
root =new TrieNode();
A new root node is created for the trie to store the dictionary words.
21 : Insert Words into Trie
for(autow: dictionary) insert(w);
Each word from the dictionary is inserted into the trie using the `insert` method.
22 : Split Sentence
istringstream ss(sentence);
The sentence is split into words using a string stream.
23 : Variable Initialization
string word ="", ans ="";
Two strings `word` and `ans` are initialized. `word` stores the current word from the sentence, and `ans` accumulates the result.
24 : Process Each Word
for(; ss>>word;) {
The loop processes each word in the sentence one by one.
25 : Word Replacement
ans += check(word);
For each word, the `check` method is called to find its replacement (prefix), which is appended to `ans`.
26 : Add Space
ans +=' ';
A space is added after each word to separate them in the final sentence.
27 : Remove Trailing Space
ans.pop_back();
The trailing space is removed from the final result.
28 : Return Final Sentence
return ans;
The final sentence, with all words replaced, is returned.
Best Case: O(n)
Average Case: O(n + m)
Worst Case: O(n * m)
Description: The time complexity is O(n * m) where n is the number of words in the sentence, and m is the length of the longest word. The best case occurs when no words are derivatives.
Best Case: O(n)
Worst Case: O(n * m)
Description: The space complexity is O(n * m) where n is the number of words in the sentence and m is the length of the longest word, due to the storage of the Trie structure.
