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.
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean end;
}
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
TrieNode root = new TrieNode();
for (String word : dictionary) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) {
node.children.put(c, new TrieNode());
}
node = node.children.get(c);
}
node.end = true;
}
String[] words = sentence.split(" ");
for (int i = 0;
i < words.length;
i++) {
TrieNode node = root;
StringBuilder shortened = new StringBuilder();
for (char c : words[i].toCharArray()) {
if (!node.children.containsKey(c)) {
break;
}
shortened.append(c);
if (node.children.get(c).end) {
break;
}
node = node.children.get(c);
}
if (shortened.length() > 0) {
words[i] = shortened.toString();
}
}
return String.join(" ", words);
}
Follow-up:
How would you optimize the solution if the dictionary is very large?
