Replace Words with Roots

Given a dictionary of roots and a sentence, replace each word by the shortest root that is its prefix; keep the word if no root fits.

1 <= d <= 1000