Решение задачи

Алгоритм решения задачи:

В отсортированном списке слов, для любого слова A[i], все предложенные слова должны следовать за этим словом в списке.

Например, если A[i] является префиксом A[j],

A[i] должен быть префиксом A[i + 1], A[i + 2], ..., A[j]

С этим наблюдением мы можем бинарно искать позицию каждого префикса поискового слова, и проверять, являются ли следующие 3 слова допустимым предложением.

Сложность

Время O(NlogN) для сортировки

Пробел O(logN) для быстрой сортировки.

Время O(logN) для каждого запроса

Пробел O (запрос) для каждого запроса

где словесная операция O (1)