All problems

Autocomplete Top Word

Medium · trie

A search box suggests words as the user types. You are given a dictionary of distinct lowercase words, where freqs[i] is how popular words[i] is (a higher number means more popular), and a list of typed prefixes.

For each prefix, suggest the most popular word in the dictionary that starts with that prefix. A word counts as starting with a prefix that is equal to the whole word. If two or more matching words are equally popular, suggest the one that comes first in alphabetical (dictionary) order. If no word starts with the prefix, suggest the empty string "".

Return a list with one suggestion per prefix, in the same order as prefixes.

Examples

Example 1

Input: words = ["car", "card", "care", "cat"], freqs = [4, 2, 7, 7], prefixes = ["ca", "car", "cart", "d"]

Output: ["care", "care", "", ""]

"care" and "cat" both have popularity 7, and "care" comes first alphabetically. For "car" the matches are "car", "card" and "care", and "care" is the most popular. Nothing starts with "cart" or "d".

Example 2

Input: words = ["to", "tea", "ten"], freqs = [3, 3, 3], prefixes = ["t", "te", "to"]

Output: ["tea", "tea", "to"]

All three words are equally popular, so the alphabetical order decides: "tea" is first among those starting with "t" or "te".

Example 3

Input: words = ["go", "gopher"], freqs = [1, 5], prefixes = ["gopher", "go", "g"]

Output: ["gopher", "gopher", "gopher"]

A word starts with a prefix equal to itself. "gopher" is more popular than "go", so it wins whenever both match.

Constraints