Replace Words

Medium· trie· prefix matching

Problem

You have a dictionary of root words and a sentence. Replace every word in the sentence that starts with some root by the shortest such root, and leave other words unchanged. Return the rewritten sentence.

Examples

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

Output: "a a b c"

Constraints

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• The sentence is lowercase words separated by single spaces

Hints & approach

Hint 1

Checking every root against every word is slow for large inputs.

Hint 2

Put the roots into a trie.

Hint 3

Walk each word down the trie and stop at the first node marked as the end of a root.

Approachtry the hints first

Insert every root into a trie with end-of-word flags. For each word in the sentence, walk the trie letter by letter; the first time you land on a node with the end flag, the prefix so far is the shortest root, so use it. If a letter has no child, or the word ends first, no root matches and the word stays as is. Join the results with spaces.

Time O(D + S), total dictionary and sentence length · Space O(D)

← PreviousImplement Trie (Prefix Tree)Next →Design Add and Search Words Data Structure