Medium · Prefix Trie Enumeration
Understand → Visualise → Practice.
Return up to limit lexicographically smallest dictionary words beginning with prefix.
Insert all words into a trie. Follow the prefix's characters, then visit the subtree depth-first with children in alphabetical order, stopping after limit words.
Insert every word, marking where words end.
Follow its characters; if a link is missing, there are no suggestions.
DFS the subtree visiting children a to z, adding complete words until you have limit of them.
O(total characters) to build; each query costs the prefix length plus the characters visited.
Visiting children in insertion order doesn't give lexicographic order.
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.