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

Древовидная структура для эффективного хранения и поиска строк. Поиск и вставка за O(L), где L — длина строки.

#1. Суть паттерна

Trie (Префиксное дерево) — это древовидная структура данных для хранения строк, где каждый узел представляет префикс. Путь от корня к узлу определяет строку, а узлы могут помечать конец слова.

#1.1 Термины

Куча (Heap) — древовидная структура, где родитель больше (max-heap) или меньше (min-heap) детей.

Дерево отрезков (Segment Tree) — структура для диапазонных запросов и обновлений.

Префиксное дерево (Trie) — дерево для хранения строк, где каждый узел представляет префикс.

Система непересекающихся множеств (DSU/Union-Find) — структура для эффективного объединения множеств и проверки принадлежности.

#Когда применять

✅ Поиск слов и префиксов — существует ли слово/префикс в словаре
✅ Автодополнение — все слова с данным префиксом
✅ Подсчёт слов с префиксом — сколько слов начинаются на префикс
✅ XOR задачи — битовый trie для максимального XOR
✅ Словарные задачи — Word Search, Add and Search Word

#Предусловия

Строковые данные — символы из ограниченного алфавита
Префиксные операции — поиск по префиксу, а не только точное совпадение
Множество слов — эффективнее hash set при многих префиксных запросах

#Структура

Слова: ["cat", "car", "cap", "dog"]

Trie:
        root
       /    \
      c      d
     / \     |
    a   o    o
   /|\   \   |
  t r  p   g g
        |
        p

Каждый узел:
┌─────────────────┐
│ children: {}    │ → {'a': Node, 'o': Node}
│ is_word: False  │ → является ли конец слова
└─────────────────┘

#Сравнение с альтернативами

Задача	Trie	Hash Set	Sorted List	BST
Поиск слова	✅ O(L)	✅ O(L)	❌ O(L × log n)	❌ O(L × log n)
Поиск префикса	✅ O(L)	❌ O(n × L)	⚠️ O(L × log n)	❌ O(n × L)
Автодополнение	✅ O(L + k)	❌ O(n × L)	⚠️ O(n × L)	❌ O(n × L)
Память	⚠️ O(n × L ×	Σ	)	✅ O(n × L)

Σ — размер алфавита

Вывод: Trie лучше для префиксных операций и автодополнения. Hash Set проще для точного поиска слов.

#2. Шаблон

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

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

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

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

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

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

#3. Разбор задач

#Задача 1: Implement Trie (LeetCode 208) 🟦 Medium

Ссылка: https://leetcode.com/problems/implement-trie-prefix-tree/

Условие: Реализуйте класс Trie (префиксное дерево) со следующими методами:

Trie() — инициализация
void insert(String word) — вставка слова
boolean search(String word) — поиск слова (возвращает true, если слово существует)
boolean startsWith(String prefix) — поиск префикса

Примеры:

Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
      [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Вывод: [null, null, true, false, true, null, true]
Объяснение:
  Trie trie = new Trie();
  trie.insert("apple");
  trie.search("apple");   // true
  trie.search("app");     // false
  trie.startsWith("app"); // true
  trie.insert("app");
  trie.search("app");     // true

Ограничения:

1 <= word.length, prefix.length <= 2000
word и prefix состоят из строчных английских букв
До 3 × 10⁴ вызовов методов

💡 Подсказка: Используйте словарь children для хранения дочерних узлов и флаг is_word для обозначения конца слова.

#Визуализация

Вставляем "cat" в пустой Trie:

Шаг 1: root → c
root
 └── c

Шаг 2: c → a
root
 └── c
     └── a

Шаг 3: a → t, помечаем is_word=True
root
 └── c
     └── a
         └── t (is_word=True)

Вставляем "car":
root
 └── c
     └── a
         ├── t (is_word=True)
         └── r (is_word=True)  ← используем существующий путь c→a

Решение:

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

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

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

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

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

    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Объяснение:

insert: проходим по символам, создаём узлы при необходимости, устанавливаем is_word = True
search: находим узел, проверяем is_word
startsWith: находим узел (не важно, is_word или нет)

Сложность:

Время: O(L) для всех операций, где L — длина слова/префикса
Память: O(n × L) в худшем случае

#Задача 2: Add and Search Word (LeetCode 211) 🟦 Medium

Ссылка: https://leetcode.com/problems/add-and-search-word-data-structure-design/

Условие: Реализуйте структуру данных WordDictionary для добавления слов и поиска по шаблону:

void addWord(String word) — добавляет слово
boolean search(String word) — поиск слова (может содержать '.' как wildcard для любой буквы)

Примеры:

Ввод: ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"]
      [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]]
Вывод: [null, null, null, null, false, true, true, true]
Объяснение:
  WordDictionary wd = new WordDictionary();
  wd.addWord("bad");
  wd.addWord("dad");
  wd.addWord("mad");
  wd.search("pad"); // false
  wd.search("bad"); // true
  wd.search(".ad"); // true (bad, dad, mad)
  wd.search("b.."); // true (bad)

Ограничения:

1 <= word.length <= 25
addWord: word из строчных английских букв
search: word из '.' или строчных английских букв
До 10⁴ вызовов методов

💡 Подсказка: Для '.' используйте DFS по всем детям узла: for child in node.children.values().

#Визуализация

Trie:
root
 └── c
     └── a
         ├── t (is_word=True)
         └── r (is_word=True)

Поиск "ca":
1. root → c ✓
2. c → a ✓
Возвращаем True (префикс существует)

Поиск "ca*":
Все слова с префиксом "ca": cat, car

Решение:

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

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

    def addWord(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return node.is_word

            if word[i] == '.':
                # Wildcard: перебираем всех детей
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False

            if word[i] in node.children:
                return dfs(node.children[word[i]], i + 1)
            return False

        return dfs(self.root, 0)

Объяснение:

addWord: стандартная вставка в Trie
search с '.': DFS по всем детям узла
search с буквой: обычный переход по Trie

Сложность:

Время: addWord O(L), search O(26^L) в худшем случае
Память: O(n × L)

#Задача 3: Word Search II (LeetCode 212) 🔴 Hard

Ссылка: https://leetcode.com/problems/word-search-ii/

Условие: Дана доска m x n с буквами и список слов. Найдите все слова из списка, которые можно составить из букв доски.

Каждую букву можно использовать только один раз в слове.

Примеры:

Ввод: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
      words = ["oath","pea","eat","rain"]
Вывод: ["eat","oath"]

Ввод: board = [["a","b"],["c","d"]], words = ["abcb"]
Вывод: []

Ограничения:

m == board.length, n == board[i].length
1 <= m, n <= 12
words.length <= 3 × 10⁴
1 <= words[i].length <= 10

💡 Подсказка: Постройте Trie из слов. Используйте DFS по доске с проходом по Trie одновременно. Это отсекает бесперспективные пути.

Решение:

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

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

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

def findWords(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    result = set()
    rows, cols = len(board), len(board[0])

    def dfs(r, c, node, path):
        if node.is_word:
            result.add(path)

        # Границы и посещённые
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if board[r][c] not in node.children:
            return

        # Помечаем как посещённый
        char = board[r][c]
        board[r][c] = '#'

        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            dfs(r+dr, c+dc, node.children[char], path + char)

        # Восстанавливаем
        board[r][c] = char

    for i in range(rows):
        for j in range(cols):
            dfs(i, j, trie.root, '')

    return list(result)

Объяснение:

Строим Trie из всех слов
DFS по доске: если board[r][c] нет в children — прерываем ветвь (pruning)
node.is_word — нашли слово, добавляем в результат
Помечаем посещённую клетку '#', затем восстанавливаем

Сложность:

Время: O(m × n × 4^L), где L — максимальная длина слова
Память: O(n × L) для Trie

#Задача 4: Maximum XOR of Two Numbers (LeetCode 421) 🟦 Medium

Ссылка: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

Условие: Дан целочисленный массив nums. Верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Примеры:

Ввод: nums = [3,10,5,25,2,8]
Вывод: 28
Объяснение: 5 XOR 25 = 28

Ввод: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Вывод: 127

Ограничения:

1 <= nums.length <= 2 × 10⁵
0 <= nums[i] <= 2³¹ - 1

💡 Подсказка: Используйте битовый Trie. Для каждого числа старайтесь выбрать противоположный бит (1→0, 0→1) для максимизации XOR.

Решение:

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

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

    def insert(self, bits):
        node = self.root
        for bit in bits:
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def find_max_xor(self, bits):
        node = self.root
        xor_bits = ''
        for bit in bits:
            toggled = '1' if bit == '0' else '0'
            if toggled in node.children:
                xor_bits += '1'
                node = node.children[toggled]
            else:
                xor_bits += '0'
                node = node.children[bit]
        return int(xor_bits, 2)

def findMaximumXOR(nums):
    trie = Trie()
    for num in nums:
        bits = format(num, '032b')
        trie.insert(bits)

    max_xor = 0
    for num in nums:
        bits = format(num, '032b')
        max_xor = max(max_xor, trie.find_max_xor(bits))

    return max_xor

Объяснение:

Представляем числа как 32-битные строки
Строим битовый Trie
Для каждого числа ищем путь с противоположными битами (максимизирует XOR)
Если противоположного бита нет, идём по имеющемуся

Сложность:

Время: O(n × 32) = O(n)
Память: O(n × 32)

#Задача 5: Concatenated Words (LeetCode 472) 🔴 Hard

Ссылка: https://leetcode.com/problems/concatenated-words/

Условие: Дан массив строк words. Верните все составные слова, которые можно образовать из двух или более слов из того же массива.

Примеры:

Ввод: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Вывод: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Объяснение:
  "catsdogcats" = "cats" + "dog" + "cats"
  "dogcatsdog" = "dog" + "cats" + "dog"
  "ratcatdogcat" = "rat" + "cat" + "dog" + "cat"

Ограничения:

1 <= words.length <= 10⁴
1 <= words[i].length <= 30
words[i] из строчных английских букв

💡 Подсказка: Постройте Trie из всех слов. Для каждого слова рекурсивно проверяйте: можно ли разбить на префикс (в Trie) + остаток (рекурсивно).

Решение:

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

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

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

def findAllConcatenatedWordsInADict(words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    result = []

    def can_form(word, count):
        """Можно ли разбить word на count+ слов из Trie"""
        if not word:
            return count > 1

        node = trie.root
        for i, char in enumerate(word):
            if char not in node.children:
                return False
            node = node.children[char]
            if node.is_word and can_form(word[i+1:], count + 1):
                return True

        return False

    for word in words:
        if can_form(word, 0):
            result.append(word)

    return result

Объяснение:

Строим Trie из всех слов
can_form(word, count): проходим по Trie, если нашли слово (is_word), рекурсивно проверяем остаток
word — составное, если можно разбить на 2+ слова из словаря

Сложность:

Время: O(n × L²) в худшем случае
Память: O(n × L) для Trie

#4. Шпаргалка

Задача	Ключевая идея
Implement Trie	children = {}, is_word
Add Search Word	DFS для '.' wildcard
Word Search II	DFS + Trie + pruning
Maximum XOR	Битовый Trie, противоположные биты
Concatenated Words	Рекурсивная проверка разбиения

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Забыли is_word флаг

Проблема: Путают существование префикса и конца слова.

# ❌ Неправильно — нет is_word
class TrieNode:
    def __init__(self):
        self.children = {}
        # Нет is_word!

# ✅ Правильно
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False  # Помечаем конец слова

Почему это неправильно: Нельзя отличить префикс от полного слова.

#❌ Ошибка 2: Неправильная обработка wildcard '.'

Проблема: Не используют DFS для wildcard.

# ❌ Неправильно — ищут '.' как обычный символ
if char in node.children:  # '.' не найдётся!

# ✅ Правильно — DFS для '.'
if char == '.':
    for child in node.children.values():
        if dfs(child, i + 1):
            return True

Почему это неправильно: '.' должен соответствовать любому символу.

#❌ Ошибка 3: Не восстанавливают доску в Word Search

Проблема: Забывают восстановить клетку после DFS.

# ❌ Неправильно — не восстанавливают
board[r][c] = '#'
dfs(r, c, index + 1)
# board остаётся '#'

# ✅ Правильно
board[r][c] = '#'
found = dfs(r, c, index + 1)
board[r][c] = char  # Восстанавливают!

Почему это неправильно: Следующие пути не смогут использовать клетку.

#❌ Ошибка 4: Не проверяют длину в Maximum XOR

Проблема: Не дополняют числа до 32 бит.

# ❌ Неправильно
for num in nums:
    bits = bin(num)[2:]  # Разная длина!

# ✅ Правильно
for num in nums:
    bits = format(num, '032b')  # Всегда 32 бита

Почему это неправильно: Разная длина битов ломает Trie.

#❌ Ошибка 5: Пропуск дубликатов в Concatenated Words

Проблема: Не проверяют, что слово состоит минимум из 2 слов.

# ❌ Неправильно
if node.is_word:
    return True  # Может вернуть True для самого слова!

# ✅ Правильно
if node.is_word and count > 1:
    return True  # Минимум 2 слова

Почему это неправильно: Слово должно состоять из других слов.

#7. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Реализуйте Trie (префиксное дерево) с методами insert, search, startsWith.

Пример:

Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
      [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Вывод: [null, null, true, false, true, null, true]

💡 Подсказка 1

Используйте вложенные словари для children

💡 Подсказка 2

is_word=True помечает конец слова

💡 Подсказка 3

startsWith не требует is_word=True

✅ Решение

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
    
    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_word
    
    def startsWith(self, prefix):
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Объяснение:

insert: проходим по символам, создаём узлы
search: ищем слово, проверяем is_word
startsWith: ищем префикс, is_word не требуется

Сложность:

Время: O(L) для всех операций, где L — длина слова/префикса
Память: O(n × L) в худшем случае

#8. Заключение

Trie эффективен для:

Поиска слов и префиксов за O(L)
Автодополнения
Задач с XOR (битовый trie)
Проверки составных слов

Оптимизации:

Pruning в Word Search II — отсечение бесперспективных путей
Сжатие координат для больших алфавитов

Слова: ["cat", "car", "cap", "dog"] Trie: root / \ c d / \ | a o o /|\ \ | t r p g g | p Каждый узел: ┌─────────────────┐ │ children: {} │ → {'a': Node, 'o': Node} │ is_word: False │ → является ли конец слова └─────────────────┘

Задача

Trie

Hash Set

Sorted List

BST

Поиск слова

✅ O(L)

❌ O(L × log n)

Поиск префикса

✅ O(L)

❌ O(n × L)

⚠️ O(L × log n)

❌ O(n × L)

Автодополнение

✅ O(L + k)

❌ O(n × L)

⚠️ O(n × L)

❌ O(n × L)

Память

⚠️ O(n × L ×

)

✅ O(n × L)

Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Вывод: [null, null, true, false, true, null, true] Объяснение: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // true trie.search("app"); // false trie.startsWith("app"); // true trie.insert("app"); trie.search("app"); // true

Вставляем "cat" в пустой Trie: Шаг 1: root → c root └── c Шаг 2: c → a root └── c └── a Шаг 3: a → t, помечаем is_word=True root └── c └── a └── t (is_word=True) Вставляем "car": root └── c └── a ├── t (is_word=True) └── r (is_word=True) ← используем существующий путь c→a

Ввод: ["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"] [[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]] Вывод: [null, null, null, null, false, true, true, true] Объяснение: WordDictionary wd = new WordDictionary(); wd.addWord("bad"); wd.addWord("dad"); wd.addWord("mad"); wd.search("pad"); // false wd.search("bad"); // true wd.search(".ad"); // true (bad, dad, mad) wd.search("b.."); // true (bad)

Trie: root └── c └── a ├── t (is_word=True) └── r (is_word=True) Поиск "ca": 1. root → c ✓ 2. c → a ✓ Возвращаем True (префикс существует) Поиск "ca*": Все слова с префиксом "ca": cat, car

Ввод: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Вывод: ["eat","oath"] Ввод: board = [["a","b"],["c","d"]], words = ["abcb"] Вывод: []

Ввод: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Вывод: ["catsdogcats","dogcatsdog","ratcatdogcat"] Объяснение: "catsdogcats" = "cats" + "dog" + "cats" "dogcatsdog" = "dog" + "cats" + "dog" "ratcatdogcat" = "rat" + "cat" + "dog" + "cat"

Задача

Ключевая идея

Implement Trie

children = {}, is_word

Add Search Word

DFS для '.' wildcard

Word Search II

DFS + Trie + pruning

Maximum XOR

Битовый Trie, противоположные биты

Concatenated Words

Рекурсивная проверка разбиения