Approach Summary
Insert all roots into a Trie. For each word, walk the Trie to the first word-end marker and use that prefix, else keep the full word.
How to Recognize This Pattern
- "Replace words with their shortest root from a dictionary"
- Trie gives O(L) prefix lookup vs O(n × L) for a set
Complexity Analysis
Time Complexity
O(∑ word lengths)
Space Complexity
O(∑ root lengths)
Tags
Array Hash Table String Trie