LeetCode 648 Replace Words - Solution

Build a trie from all roots. For each word in the sentence, walk through the trie. The first complete root you encounter is the shortest one.

If you reach a node marked as a root ending, return that prefix. If you exhaust the word without finding a root, keep the original word.

The trie lets you find the shortest matching prefix in $O(m)$ time per word, where $m$ is word length.