Replace Words

Given a dictionary of root words and a sentence, replace every word in the sentence with the shortest root that is a prefix of it. Words with no matching root stay unchanged.

1 <= d <= 1000 1 <= len(sentence) <= 10^6