Replace Words
In English, we have a concept called a 'shortened word'. A shortened word is created by taking we remove the vowels from a word and keep the consonants in the same order. For example, the word "word" becomes "wrld". Given a list of words and a sentence, replace all words in the sentence with their shortened versions if they exist in the list.
Constraints:
- 1 <= words.length <= 100
- 1 <= sentence.length <= 1000
Examples:
Input: ["cat","bat","hat"], "the cat is in the hat"
Output: the cat is in the hat
Explanation: The word "cat" and "hat" are in the list, so they are replaced with their shortened versions, but "the" is not in the list, so it remains the same.
Solutions
Trie-based approach
We create a Trie and insert all words from the dictionary into it. Then we iterate over each word in the sentence and check if it exists in the Trie. If it does, we replace it with its shortened version.
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool end;
}
;
class Solution {
public:
string replaceWords(vector<string>& dictionary, string sentence) {
TrieNode* root = new TrieNode();
for (const string& word : dictionary) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->end = true;
}
istringstream iss(sentence);
string word;
vector<string> words;
while (iss >> word) {
TrieNode* node = root;
string shortened;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
break;
}
shortened += c;
if (node->children[c]->end) {
break;
}
node = node->children[c];
}
if (!shortened.empty()) {
word = shortened;
}
words.push_back(word);
}
string result;
for (const string& word : words) {
result += word + " ";
}
result.pop_back();
return result;
}
}
;
Follow-up:
How would you optimize the solution if the dictionary is very large?
