LeetCode 648 Replace Words - Why Naive Fails

For each word, check every root to see if the word starts with it. Keep the shortest matching root.

With $d$ roots and $w$ words, each of average length $m$, checking all combinations is $O(d \cdot w \cdot m)$.

For large dictionaries and sentences, this is slow. Can you find the shortest root faster?