Search box suggestions

A search box shows suggestions while you type. SearchBox(pairs) receives every word with its count (how often people searched for it). suggest(prefix) returns the three words with the highest counts among the words that start with the prefix, highest first. Equal counts are broken by alphabetical order. If fewer than three words match, return them all; if none match, return [].

b = SearchBox([("tea", 5), ("ten", 9), ("team", 2),
               ("to", 7), ("toe", 1)])
b.suggest("te")    # ['ten', 'tea', 'team']
b.suggest("t")     # ['ten', 'to', 'tea']
b.suggest("to")    # ['to', 'toe']
b.suggest("x")     # []

A word counts as starting with itself. Words and prefixes are non-empty and use the letters a to z.

Limits

• Up to 20,000 words of at most 8 letters, and 20,000 suggestions.
• A suggestion must not depend on how many words match: it should cost O(L) for a prefix of length L. Building the search box may cost more.