Trie (префиксное дерево)

O(len) per op

Храните слова в дереве, где каждый узел содержит один символ, а путь от корня складывается в префикс. Слова с общим началом делят одни и те же узлы, поэтому вставка/поиск/проверка префикса стоят лишь длину слова.

Сигналы

автодополнение или typeahead по множеству строксамый длинный общий префикс среди словвставка, поиск и проверка префикса в наборе словсопоставление с большим фиксированным словарём по префиксу

Шаблон

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}
class Trie {
    constructor() { this.root = new TrieNode(); }
    insert(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) node.children.set(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }
    search(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) return false;
            node = node.children.get(c);
        }
        return node.isEnd;
    }
}

Похоже, но не то

Хеш-множество / хеш-карта: Хеш-множество или хеш-карта отвечают на вопрос о точном совпадении ключа за O(1), но не имеют понятия о том, что одна строка является префиксом другой. Trie делит хранение общих префиксов и идёт по символам, поэтому именно он отвечает на вопросы про автодополнение и самый длинный префикс, с которыми хеш-карта не справится.

до 1e5 слов длиной до L, один проход по символам -> O(len) на вставку/поиск/проверку префикса, независимо от того, сколько ещё слов хранится.

Изучить этот паттерн