catalog, a list of unique names. A shopper types the string query into the search box one letter at a time.
After every letter, the search box shows suggestions: the products whose names start with the part of query typed so far. If more than three products match, it shows the three that come first alphabetically, and the suggestions themselves are listed in alphabetical order.
Return a list of length len(query) whose i-th entry holds the suggestions after the first i + 1 letters have been typed. If nothing matches, that entry is an empty list.catalog=["lamp", "lantern", "ladder", "lace", "latch", "mug"], query="lan" → [['lace', 'ladder', 'lamp'], ['lace', 'ladder', 'lamp'], ['lantern']]
After "l" and "la" five items match, and the first three alphabetically are lace, ladder, lamp. After "lan" only lantern is left.
catalog=["pen", "pencil"], query="pin" → [['pen', 'pencil'], [], []]
Both items match "p", but nothing starts with "pi", so the remaining lists are empty.
catalog=["tea"], query="tea" → [['tea'], ['tea'], ['tea']]
catalog is at most 2·10⁴query consists of lowercase English letterscatalog=["lamp", "lantern", "ladder", "lace", "latch", "mug"], query="lan"
[['lace', 'ladder', 'lamp'], ['lace', 'ladder', 'lamp'], ['lantern']]
Run checks the first 3 tests in your browser. Submit checks all 86 tests on the server, hidden ones included.