Что такое Trie (префиксное дерево)?

Trie (prefix tree) — дерево для хранения строк с shared prefixes. Каждый узел — буква, путь от root = слово. Операции O(L), где L = длина слова, не зависят от количества слов.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

Применения: autocomplete, spell check, IP routing (longest prefix), dictionary. Space — O(total chars). Вариации: compressed trie (Patricia/Radix tree), suffix tree. Word Search II (LeetCode 212) — Trie + DFS backtracking.