Replace Words
Implement replaceWords
Given a list of shorter "root" words and a
sentence, replace every word in the sentence that has one of the roots as a prefix with that root — the shortest one, if more than one root matches. Words with no matching root pass through unchanged.
Checking a word against every root one at a time works, but it repeats the same character comparisons across similar words. Building a trie of the roots instead means walking a word down it costs only as many steps as the word has characters before either falling off (no root matches) or landing on a node marking a complete root — and since that walk naturally proceeds shortest-prefix-first, the first root it finds is guaranteed to be the shortest one, with no length comparison needed at all.
Example 1:
Input: roots = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Example 2:
Input: roots = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs zifzif"
Output: "a a b c zifzif"
Example 3:
Input: roots = ["a","aa"], sentence = "a aa aaa aaaa"
Output: "a a a a"
+ 7 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ roots.length ≤ 1000 - ●
1 ≤ roots[i].length ≤ 20 - ●
1 ≤ sentence.length ≤ 1000 - ●
roots[i] and every word in sentence consist of lowercase English letters - ●
sentence is a single space-separated string with no leading, trailing, or doubled spaces
roots =
["cat", "bat", "rat"]
sentence =
the cattle was rattled by the battery