Где применяется
1. Задача
Шаг 129 построил trie (префиксное дерево). Он вставляет слова и отвечает на два вопроса: «есть ли такое слово?» и «начинается ли что-нибудь с этих букв?». Пока дерево только росло. Теперь слова должны и удаляться. Пользователь добавил имя в свой словарь, потом понял, что ошибся, и убрал его. Подсказки должны перестать предлагать это слово сразу.
Снять пометку isEnd мало. Узлы, из которых было составлено слово, тогда останутся навсегда, хотя ни одному слову они уже не нужны. После тысяч добавлений и удалений дерево зарастёт путями, которые никуда не ведут. Нужно, чтобы слово исчезло и его бесполезные теперь узлы были срезаны. Узлы, которые нужны другим словам, должны остаться.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
LeetCode не просит удалить слово из trie и обрезать мёртвые ветки. Implement Trie II (1804), единственная задача с удалением, платная. Обрезка пригодится в Word Search II из урока 142, где каждое найденное слово вырезают из trie, чтобы поиск по сетке больше туда не заходил. Бесплатные задачи на trie есть в уроках 129 и 131.