930. Replace Words Using Trie (Sentence Shortening)

Given a list of root words and a sentence, replace every word in the sentence with the shortest root that is a prefix of it (if any such root exists); otherwise keep the word unchanged. Return the resulting sentence. The input is JSON {roots, sentence}.

Input: JSON {roots, sentence}.

Output: Quoted string — the transformed sentence.

Examples

Input: {"roots":["cat","bat","rat"],"sentence":"the cattle was rattled by the battery"}
Output: "the cat was rat by the bat"
Explanation: Each word shortened to its root.

Input: {"roots":["a","b","c"],"sentence":"aadsfasf absbs bbab cadsfafs"}
Output: "a a b c"
Explanation: Single-letter roots.

Input: {"roots":["se"],"sentence":"success is here"}
Output: "se is here"
Explanation: Only 'success' has a root.

Constraints

• 1<=roots<=10^4
• 1<=words<=10^4
• lowercase letters

Asked by