Autocomplete Suggestions

A search box suggests words as you type. Build an Autocomplete class:

• Autocomplete() starts with no words.
• add(word) stores a word. Adding a word that is already stored changes nothing.
• suggest(prefix) returns the first three stored words in alphabetical order that start with prefix, as a list (fewer if fewer words match, and an empty list if none do). A word counts as starting with itself, and the empty prefix matches every word.

Examples

ac = Autocomplete()
for w in ['car', 'card', 'care', 'cart', 'cat', 'dog']:
    ac.add(w)
ac.suggest('car')    # returns ['car', 'card', 'care']
ac.suggest('cat')    # returns ['cat']
ac.suggest('d')      # returns ['dog']
ac.suggest('z')      # returns []

Constraints

• Words and prefixes use the lowercase letters a to z; words have 1 to 20 letters
• Up to 50,000 calls of add and 20,000 calls of suggest, mixed in any order
• Checking every stored word on each suggest call is too slow at that size.