Три подсказки при наборе

Средняя

В интернет-магазине есть каталог товаров catalog — список уникальных названий. Пользователь по одной букве набирает в поиске строку query. После каждой набранной буквы строка поиска показывает подсказки: товары, названия которых начинаются с уже набранной части query. Если таких товаров больше трёх, показываются три первых по алфавиту; подсказки тоже идут по алфавиту. Верните список длины len(query): на i-м месте — подсказки после ввода первых i + 1 букв. Если ничего не подходит, на этом месте пустой список.

Пример 1

catalog=["lamp", "lantern", "ladder", "lace", "latch", "mug"], query="lan" → [['lace', 'ladder', 'lamp'], ['lace', 'ladder', 'lamp'], ['lantern']]

После «l» и «la» подходят пять товаров, по алфавиту первые три — lace, ladder, lamp. После «lan» остаётся только lantern.

Пример 2

catalog=["pen", "pencil"], query="pin" → [['pen', 'pencil'], [], []]

На «p» подходят оба товара, а с «pi» не начинается ничего — дальше списки пустые.

Пример 3

catalog=["tea"], query="tea" → [['tea'], ['tea'], ['tea']]

Ограничения

1 ≤ len(catalog) ≤ 1000
Суммарная длина названий в catalog ≤ 2·10⁴
Все названия различны, непустые и состоят из строчных латинских букв
1 ≤ len(query) ≤ 1000, query состоит из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Trie Array String Binary Search Sorting Heap (Priority Queue)

Вход

catalog=["lamp", "lantern", "ladder", "lace", "latch", "mug"], query="lan"

Ожидается

[['lace', 'ladder', 'lamp'], ['lace', 'ladder', 'lamp'], ['lantern']]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 86 тестов на сервере, включая скрытые.