Approach #1: Prefix Hash [Accepted]
Intuition
For each word in the sentence, we'll look at successive prefixes and see if we saw them before.
Algorithm
Store all the roots
in a Set structure. Then for each word, look at successive prefixes of that word. If you find a prefix that is a root, replace the word with that prefix. Otherwise, the prefix will just be the word itself, and we should add that to the final sentence answer.
Complexity Analysis

Time Complexity: where is the length of the th word. We might check every prefix, the th of which is work.

Space Complexity: where is the length of our sentence; the space used by
rootset
.
Approach #2: Trie [Accepted]
Intuition and Algorithm
Put all the roots in a trie (prefix tree). Then for any query word, we can find the smallest root that was a prefix in linear time.
Complexity Analysis

Time Complexity: where is the length of the
sentence
. Every query of a word is in linear time. 
Space Complexity: , the size of our trie.
Analysis written by: @awice.