Replace Words
Medium · Trie · about 15 minutes
Asked at Uber, Amazon, LinkedIn.
Given a dictionary of root words and a sentence of space-separated words, replace every word that starts with a root by the shortest such root. Return the resulting sentence.