Replace Words With Their Roots

roots is a list of root words. In the sentence (words separated by single spaces), replace every word that starts with a root by the shortest root it starts with. Words without a root stay as they are. Return the new sentence.

For roots = ["cat", "bat", "rat"] and sentence = "the cattle was rattled by the battery" the answer is "the cat was rat by the bat".

The starter code tries every root for every word. It is correct but too slow with many roots and words.

Examples

Example 1

Input:

replace_words(['cat', 'bat', 'rat'], 'the cattle was rattled by the battery')

Output:

'the cat was rat by the bat'

Example 2

Input:

replace_words(['a', 'b', 'c'], 'aadsfasf absbs bbab cadsfafs')

Output:

'a a b c'

Constraints

• 0 <= len(roots) <= 5000
• 0 <= number of words in the sentence <= 20000
• Lower-case letters; words and roots are 1 to 20 long.