Префиксное дерево (trie)

Trie (бор, префиксное дерево) хранит строки по символам: общие префиксы делят общий путь. Идеально для автодополнения и проверки префиксов.

Сложность: вставка и поиск — O(L), где L — длина ключа, независимо от числа слов. Память: O(сумма длин всех ключей) — может быть большой из-за узлов на каждый символ.

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):       # O(L)
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True

    def search(self, word):       # O(L)
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return "$" in node