Replace Words With Their Roots

You are given a list of root words roots and a sentence of words separated by single spaces. Replace every word in the sentence that starts with a root by the shortest such root. Words that start with no root stay unchanged. Return the new sentence.

Examples

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

Input:  roots = ["a", "aa"], sentence = "aaa aab b"
Output: "a a b"

Constraints

• 0 <= len(roots) <= 10**4, roots are non-empty lowercase strings
• sentence contains up to 10**4 words of lowercase letters; it may be empty
• Target: O(total root characters + total sentence characters)

Goals

• Stop a trie walk as soon as a stored word ends
• Rebuild a sentence word by word