All problems

Replace Words

Medium · trie

A dictionary holds short word roots, such as "help", that longer words can be built from, such as "helpful" or "helper". Given a list of roots dictionary and a sentence made of words separated by single spaces, replace each word with the shortest root that is a prefix of it.

If a word has no root as a prefix, leave it unchanged. Return the sentence after all replacements.

Examples

Example 1

Input: dictionary = ["app", "ban"], sentence = "apple banana bandit cherry"

Output: "app ban ban cherry"

"apple" starts with "app" and both "banana" and "bandit" start with "ban". "cherry" matches no root, so it stays.

Example 2

Input: dictionary = ["go", "gopher"], sentence = "gopher goes going"

Output: "go go go"

Both roots are prefixes of "gopher", and the shorter one, "go", wins.

Example 3

Input: dictionary = ["zebra"], sentence = "zeb zebra zebras"

Output: "zeb zebra zebra"

A root longer than the word is not a prefix of it, so "zeb" is unchanged.

Constraints

• 1 <= len(dictionary) <= 1000
• 1 <= len(dictionary[i]) <= 100, lowercase English letters only
• 1 <= len(sentence) <= 10^4, lowercase letters and single spaces, no leading or trailing space
• Every word in sentence has between 1 and 1000 letters
• The dictionary may contain duplicates.