Сигнал задачи
Когда применять
Много запросов разделяют строковые префиксы.
Что держать в голове
- Уметь объяснять разделение общих префиксов в trie.
- Уметь реализовывать insert, contains и hasPrefix.
Сложность
- Вставка и поиск слова длины L занимают O(L); память пропорциональна числу созданных переходов.
Границы и ошибки
- Признак terminal обязателен: существующий путь префикса ещё не означает, что полное слово было добавлено.