Replace Words

In English, we have a concept called root, which can be followed by some other word to form another longer word — let us call that word a derivative. For example, when the root "help" is followed by "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Examples

Example 1:

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

Output: "the cat was rat by the bat"

Explanation: "cattle" is replaced by "cat" (root), "rattled" is replaced by "rat", and "battery" is replaced by "bat".

Example 2:

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

Output: "a]" a b c"

Explanation: Every word starts with a root from the dictionary, so each is replaced by the shortest matching root.

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: The shortest root "a" replaces any word starting with "a". Words not matching any root remain unchanged.

Constraints

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lowercase letters
• 1 <= sentence.length <= 10⁶
• sentence consists of only lowercase letters and spaces
• The number of words in sentence is in the range [1, 1000]
• The length of each word in sentence is in the range [1, 1000]
• Every two consecutive words in sentence will be separated by exactly one space
• sentence does not have leading or trailing spaces