Войти Регистрация
Алгоритмы

206. Сколько запросов подходит под набранное начало

Средняя

В словаре подсказок Яндекс Поиска лежат запросы queries (повторы — отдельные запросы). Пользователи набирают начала typed.

Для каждой строки из typed верните, сколько запросов из queries начинаются с неё. Пустое начало подходит ко всем запросам.

В работе: Подсказки решают, показывать ли «ещё N вариантов»: словарь на 10⁵ запросов и 10⁵ наборов в минуту, проверка `startswith` по всему словарю — 10¹⁰ сравнений.

Пример 1

Ввод
queries = ["погода", "погода завтра", "почта", "поезд", "погода"]
typed = ["пог", "по", "погода з", "так"]
Вывод
[3, 5, 1, 0]

«пог» — три запроса, из них два одинаковых.

Пример 2

Ввод
queries = ["а"]
typed = [""]
Вывод
[1]

Пустое начало подходит ко всему.

Ограничения

  • 1 ≤ длина queries ≤ 10⁵
  • 1 ≤ длина typed ≤ 10⁵
  • суммарная длина строк ≤ 10⁶
  • Лимит — 2 с на тест (2500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def prefix_counts(queries, typed):
Префиксное деревоСтрокицельO(n)

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.