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:
def __init__(self):
self.children = {}
self.end = False
class Solution:
def replaceWords(self, dictionary:
List[str], sentence:
str) -> str:
root = TrieNode()
for word in dictionary:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.end = True
words = sentence.split()
for i in range(len(words)):
node = root
shortened = ''
for char in words[i]:
if char not in node.children:
break
shortened += char
if node.children[char].end:
break
node = node.children[char]
if shortened:
words[i] = shortened
return ' '.join(words)
Follow-up:
How would you optimize the solution if the dictionary is very large?
