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 time per word, where is word length.