Solution: Replace Words
Let's solve the Replace Words problem using the Trie pattern.
Statement
In this problem, we are considering the words that are composed of a
You’re given a dictionary, dictionary
, consisting of prefixes, and a sentence, sentence
, which has words separated by spaces only. Your task is to replace the postfix in sentence
with their prefixes given in dictionary
(if found) and return the modified sentence.
A couple of points to keep in mind:
-
If a postfix in the sentence matches more than one prefix in the dictionary, replace it with the prefix that has the shortest length. For example, if we have the sentence “iphone is amazing”, and the dictionary {“i”, “ip”, “hone”}, then the word “iphone” has two prefixes in the dictionary “i” and “ip”, but we will replace it with the one that is shorter among the two, that is, “i”.
-
If there is no root word against any word in the sentence, leave it unchanged.
Constraints:
-
dictionary.length
-
dictionary[i].length
dictionary[i]
consists of only lowercase letters.-
sentence.length
- The number of words in
sentence
is in the range . - The length of each word in
sentence
is in the range . - Two consecutive words in
sentence
should be separated by exactly one space. - All words in
sentence
are lowercase. - For a word in
sentence
, the length of a prefix can be , and the length of a postfix can be .
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.