Given a list of lowercase strings words and a query string prefix, return all words that start with prefix, in lexicographic order. If no words match, return an empty list. Your solution should support repeated queries efficiently.
Constraints
1 <= len(words) <= 10^5
1 <= len(words[i]) <= 50
1 <= len(prefix) <= 50
words[i] and prefix contain only lowercase English letters
The same prefix may be queried many times
Interviewer
Your question is Prefix Search with Autocomplete. Start with the requirements in the Question tab.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
