Ранее мы уже разбирали задачу, в которой нужно было реализовать структуру данных trie. В этом посте я решил рассмотреть более прикладную задачу, связанную с использованием этой структуры.
Классические задачи для префиксного дерева включают поиск по префиксу: например, нахождение конкретного слова или подготовка автодополнений (саджестов) по заданным префиксам.
На первый взгляд, текущая задача кажется типичной: требуется найти саджесты по префиксу. К сожалению, в этот раз я прогадал: в задаче нужно взять массив продуктов и единожды найти множество саджестов по префиксу. Если переформулировать, пишущая нагрузка (любое преобразование входящего массива) либо сопоставима, либо выше читающей. В реальных приложениях такое редко встречается — чаще доминирует чтение.
Таким образом, хотя использование префиксного дерева могло бы быть разумным выбором в реальных условиях, для оптимального решения данной задачи на литкоде эта структура данных оказалась не самой удачной.
Сложность: 🟡 Средняя
ℹ️ Описание
Дан массив строк products, представляющий доступные названия продуктов, и строка searchWord, представляющая искомое слово, вводимое пользователем.
Реализуйте функцию, которая возвращает массив массивов, где:
— Каждый подмассив содержит список подсказок для соответствующего префикса строки searchWord. Первый подмассив соответствует префиксу из первого символа строки searchWord, второй — префиксу из первых двух символов, и так далее.
— Каждый подмассив включает до трех продуктов из products, отсортированных в лексикографическом порядке.
— Если для какого-либо префикса не найдено совпадений, соответствующий подмассив должен быть пустым.
⚠️ Ограничения
— 1 <= products.length <= 1000 — количество продуктов.
— 1 <= products[i].length <= 3000 — длина каждой строки продукта.
— 1 <= searchWord.length <= 1000 — длина строки поиска.
— Все строки состоят только из строчных латинских букв.
1️⃣ Пример
Продукты: products = ["mobile","mouse","moneypot","monitor","mousepad"]
Искомое слово: searchWord = "mouse"
Ответ:
[
["mobile","moneypot","monitor"], // список подсказок для префикса "m"
["mobile","moneypot","monitor"], // список подсказок для префикса "mo"
["mouse","mousepad"], // список подсказок для префикса "mou"
["mouse","mousepad"], // список подсказок для префикса "mous"
["mouse","mousepad"], // список подсказок для префикса "mouse"
]
2️⃣ Пример
Продукты: products = ["havana"]
Искомое слово: searchWord = "havana"
Ответ:
[
["havana"], // список подсказок для префикса "h"
["havana"], // список подсказок для префикса "ha"
["havana"], // список подсказок для префикса "hav"
["havana"], // список подсказок для префикса "hava"
["havana"], // список подсказок для префикса "havan"
["havana"], // список подсказок для префикса "havana"
]
✅ Реализация
Как я писал в начале, первое что приходит в голову для решения этой задачи — преобразовать исходный массив в дерево и обходить его в глубину.
➡️ Решение через преобразование в префиксное дерево
Задача разделяется на 2 подзадачи:
— Имплементировать структуру данных Trie и преобразовать входящий массив
— Имплементировать метод Closest, который по префиксу вернет массив подсказок.
Помимо этого есть несколько решений по оптимизации: например, можно обходить дерево с самого большого возможного префикса. Тогда можно реализовать "всплытие" подсказок и избежать лишних обходов в глубину. Или же можно пожертвовать памятью и для каждого узла дерева сохранять набор подсказок в момент добавления нового слов.
➡️ Решение через бинарный поиск