Код Senior Реализация с нуля обновлено
Префиксное дерево
Условие
createTrie(): insert(word), has(word) - точное совпадение, startsWith(prefix), suggest(prefix, limit) - слова с этим префиксом в порядке вставки.
Что проверяют тесты
точное совпадение
префикс
подсказки
ограничение количества
нет такого префикса
Как подойти
Префиксное дерево даёт поиск по префиксу за длину префикса, независимо от размера словаря. Хранение самого слова в конечном узле вместо флага избавляет от склеивания символов при обходе. Именно так устроены автодополнение в поисковой строке и фильтрация больших справочников на клиенте. Сравнение: перебор массива с startsWith - O(n·k) на каждый ввод символа.
Подсказки: 3
- Узел хранит детей по символу и признак конца слова.
- Признаком конца лучше сделать само слово - тогда его не надо собирать заново.
- Подсказки - обход поддерева от узла префикса.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.