Search Suggestions System

Средняя№1268вставка и поиск

Есть список товаров и слово, которое набирают. После каждой набранной буквы нужно подсказать до трёх товаров, начинающихся с уже набранных букв, — первые по алфавиту. Вернуть по списку на каждую букву. Наш пример: товары [ox, on, of, or], набирают «oxen» — ответ [[of, on, or], [ox], [], []].

1268 Search Suggestions SystemРазбор · 1×

Пример: товары [ox, on, of, or], searchWord «oxen». Каждый узел хранит до 3 подсказок: строка node.top показывает их у текущего узла.

rootproductsnode.top—productsoxonoforрезультат
в дереветолько что добавленопройденный путь; сохранённая подсказкатекущий узел и товарнет такой буквы

Сортируем товары: [ox, on, of, or] становится [of, on, or, ox]

01/68
сначала · назад · пуск · шаг
Скорость
1function suggestedProducts(products, searchWord):
2 sort products
3 root = new node // node.top: its first 3 words
4 for each word in products:
5 node = root
6 for each ch in word:
7 if ch not in node.children:
8 node.children[ch] = new node
9 node = node.children[ch]
10 if len(node.top) < 3:
11 append word to node.top
12 result = []
13 node = root
14 for each ch in searchWord:
15 if node is not none:
16 node = node.children.get(ch) // or none
17 append (node.top if node else []) to result
18 return result
состояние
products
[ox, on, of, or]
word
–
ch
–
node
–
node.top
–
result
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждый товар, который начинается с префикса, при вставке проходит через узел этого префикса, поэтому узел видит всех своих кандидатов.
  2. Товары вставляются в отсортированном порядке, поэтому первые 3, прошедшие через узел, — это 3 самых маленьких, и набрав 3, узел может больше не брать слова.
  3. Набор букв — шаг на узел за букву. Если буквы нет, ни один товар не начинается с набранного, а значит, и с любого более длинного префикса, поэтому все следующие списки — [].

Сложность

Время O(n log n · L) на сортировку n товаров длиной до L букв, плюс O(суммы длин) на вставку и O(len(searchWord)) на набор: каждый список уже лежит в узле. Память O(суммы длин): узел на букву и не больше 3 слов в нём.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.