Replace words with shortest root

Write codeMedium25 minGoogle style

Your task

Given a list of root words roots and a sentence of space-separated lowercase words, replace every word in the sentence with the SHORTEST root in roots that is a prefix of it; if no root is a prefix, keep the word unchanged. Return the resulting sentence as a single space-separated string. Words and roots are lowercase. 0 <= len(roots) <= 1000.

Examples

replace_words(roots: list[str], sentence: str) -> str

Example 1

Inputreplace_words(["cat", "bat", "rat"], "the cattle was rattled by the battery")

Output"the cat was rat by the bat"