Shorthand Rewriter

medium

A newsroom style guide keeps a dictionary of roots — approved short forms. House style says any word that begins with a root must be printed as that root: if "cat" is a root, "cattle" runs as "cat".

Given roots and a sentence of space-separated lowercase words, replace every word that has a root prefix with its shortest such root (some roots may themselves extend other roots), leave other words untouched, and return the rewritten sentence.

Example 1

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

out "the cat was rat by the bat"

Example 2

in roots = ["co", "code"], sentence = "coding contest"

out "co co"

Both roots prefix "coding"; the shortest one, "co", wins.

Constraints

· 1 <= len(roots) <= 1000
· 1 <= len(roots[i]) <= 100
· sentence has 1 to 1000 lowercase words separated by single spaces