Почему это работает
- Каждый товар, который начинается с префикса, при вставке проходит через узел этого префикса, поэтому узел видит всех своих кандидатов.
- Товары вставляются в отсортированном порядке, поэтому первые 3, прошедшие через узел, — это 3 самых маленьких, и набрав 3, узел может больше не брать слова.
- Набор букв — шаг на узел за букву. Если буквы нет, ни один товар не начинается с набранного, а значит, и с любого более длинного префикса, поэтому все следующие списки — [].
Сложность
Время O(n log n · L) на сортировку n товаров длиной до L букв, плюс O(суммы длин) на вставку и O(len(searchWord)) на набор: каждый список уже лежит в узле. Память O(суммы длин): узел на букву и не больше 3 слов в нём.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗