Где применяется
1. Задача
Ты набираешь «app» в строке поиска, и под ней сразу появляется список: «apple», «application», «apply». Список обновляется на каждое нажатие клавиши, а в словаре может быть миллион слов. На прошлом шаге ты построил trie (префиксное дерево). Он отвечает «да» или «нет» на вопрос, начинается ли какое-нибудь слово с этих букв. Автодополнению этого мало. Ему нужны сами слова, которые начинаются с «app», в определённом порядке и в разумном количестве. На этом шаге trie научится выдавать подсказки.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно перечислить или оценить все слова под префиксом, например подсказки при поиске или сумму значений по префиксу. Спустись до узла префикса, и DFS под ним в порядке букв выдаст слова уже отсортированными.
Задача урока. После каждой набранной буквы спустись к узлу префикса и верни первые три слова из DFS.
Храни значение каждого ключа в его конечном узле, а sum(prefix) складывает все значения в поддереве под префиксом.
Вставь все слова, потом иди DFS только по узлам, где кончается слово, и запомни самое длинное, а при равной длине наименьшее.
Считай в каждом узле, сколько слов через него проходит, и оценка слова это сумма счётчиков на его пути.