Где применяется
1. Задача
Ты набираешь app в строке поиска, и под ней сразу появляется список: apple, apply, application. Это происходит на каждое нажатие клавиши, по словарю из тысяч слов, без заметной задержки.
Обычное множество слов (Set) быстро отвечает на вопрос «есть ли apple в списке?»: по хешу слова оно сразу находит нужное место и другие слова не перебирает. На вопрос «начинается ли хоть одно слово с app?» так ответить нельзя. Множество хранит каждое слово отдельно, общие начала слов в нём никак не связаны, и придётся проверить каждое слово.
Нужно, чтобы быстрым был именно вопрос про начало слова (префикс). Набрал три буквы, получил ответ, не просматривая весь словарь.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитinsert("car"), insert("cat"), insert("dog"), search("cat"), search("ca"), search("cow")Сохраняем ["car", "cat", "dog"], чтобы искать их буква за буквой. Корень означает пустой префикс.
Как узнать
Эти слова в условии значат этот паттерн
- автодополнение или typeahead по множеству строк
- самый длинный общий префикс среди слов
- вставка, поиск и проверка префикса в наборе слов
- сопоставление с большим фиксированным словарём по префиксу
Похоже, но не то
- Хеш-множество / словарь (Hash set / map)
Словарь сравнивает только целые ключи. Trie отвечает ещё и на запросы по префиксу.
- Двоичное дерево поиска (Binary search tree)
Дерево поиска сравнивает целые ключи и выбирает сторону. Trie идёт по одному символу.
- Поиск слова в матрице (DFS/backtracking по сетке) (Matrix word search (grid DFS/backtracking))
Поиск многих слов в сетке использует trie для обрезки. Та страница про сам обход сетки.
- DP на строках (word break) (DP on strings (word break))
Разбиение на слова использует trie для проверки куска. Решение о разрезе лежит в таблице.
Слово длины m стоит O(m) на вставку или поиск. Память O(суммы символов) по всем словам.
На LeetCode
Задачи, где хранят много слов и спрашивают о префиксах, например есть ли слово или префикс, какой самый короткий корень начинает слово или как искать, когда точка стоит на месте любой буквы. Каждый символ это один шаг вниз по trie, так что поиск стоит длину слова.
Задача урока слово в слово.
Вставь все слова и спускайся от корня, пока у узла ровно один ребёнок и на нём не кончается слово.
Вставь корни, а потом для каждого слова спускайся и остановись на первом узле, где кончается корень.
Точка совпадает с любой буквой, так что на точке пробуй каждого ребёнка узла через DFS.