Given a dictionary of root words and a sentence, replace every word with the shortest dictionary root that is its prefix. Pattern focus: Trie Prefix Counting. The key is to stop at the earliest terminal root while scanning each word.
dictionary = array of root words, sentence = space-separated text
sentence after root replacement
Example 1:
Input:
dictionary = ["cat","bat","rat"] sentence = "the cattle was rattled by the battery"
Output:
the cat was rat by the bat
Explanation:
The shortest matching root should replace each affected word.
Example 2:
Input:
dictionary = ["cat","dog"] sentence = "the quick brown fox"
Output:
the quick brown fox
Explanation:
When no root matches, the sentence remains unchanged.
Example 3:
Input:
dictionary = ["a","aa","aaa","aaaa"] sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output:
a a a a a a a a bbb baba a
Explanation:
Overlapping roots should always resolve to the shortest valid one.