Medium · Shortest Prefix Trie
Understand → Visualise → Practice.
Replace every sentence word by its shortest dictionary root prefix when one exists.
Put the roots in a trie. For each word, walk its letters and stop at the first node that ends a root; that is the shortest root. If you fall off the trie, keep the word.
Insert every root and mark its end.
Follow its letters until a root ends or the path breaks.
Use the root found, otherwise the original word; join with spaces.
O(total characters) time and O(total root characters) space.
Choosing the longest matching root instead of the shortest gives the wrong replacement.
Read the full guide first: Tries and Prefix Search.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.