Префиксные деревья для хранения строк. Поиск, автодополнение, XOR-пары.
Древовидная структура для эффективного хранения и поиска строк. Поиск и вставка за O(L), где L — длина строки.
Trie (Префиксное дерево) — это древовидная структура данных для хранения строк, где каждый узел представляет префикс. Путь от корня к узлу определяет строку, а узлы могут помечать конец слова.
Куча (Heap) — древовидная структура, где родитель больше (max-heap) или меньше (min-heap) детей.
Дерево отрезков (Segment Tree) — структура для диапазонных запросов и обновлений.
Префиксное дерево (Trie) — дерево для хранения строк, где каждый узел представляет префикс.
Система непересекающихся множеств (DSU/Union-Find) — структура для эффективного объединения множеств и проверки принадлежности.
Слова: ["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 проще для точного поиска слов.
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Условие:
Реализуйте класс 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
Ограничения:
💡 Подсказка: Используйте словарь 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Объяснение:
Сложность:
Условие:
Реализуйте структуру данных 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)
Ограничения:
💡 Подсказка: Для '.' используйте 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)Объяснение:
Сложность:
Условие:
Дана доска 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"]
Вывод: []
Ограничения:
💡 Подсказка: Постройте 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)Объяснение:
Сложность:
Условие:
Дан целочисленный массив 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
Ограничения:
💡 Подсказка: Используйте битовый 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Объяснение:
Сложность:
Условие:
Дан массив строк 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"
Ограничения:
💡 Подсказка: Постройте 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Объяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| Implement Trie | children = {}, is_word |
| Add Search Word | DFS для '.' wildcard |
| Word Search II | DFS + Trie + pruning |
| Maximum XOR | Битовый Trie, противоположные биты |
| Concatenated Words | Рекурсивная проверка разбиения |
Проблема: Путают существование префикса и конца слова.
# ❌ Неправильно — нет is_word
class TrieNode:
def __init__(self):
self.children = {}
# Нет is_word!
# ✅ Правильно
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False # Помечаем конец словаПочему это неправильно: Нельзя отличить префикс от полного слова.
Проблема: Не используют DFS для wildcard.
# ❌ Неправильно — ищут '.' как обычный символ
if char in node.children: # '.' не найдётся!
# ✅ Правильно — DFS для '.'
if char == '.':
for child in node.children.values():
if dfs(child, i + 1):
return TrueПочему это неправильно: '.' должен соответствовать любому символу.
Проблема: Забывают восстановить клетку после DFS.
# ❌ Неправильно — не восстанавливают
board[r][c] = '#'
dfs(r, c, index + 1)
# board остаётся '#'
# ✅ Правильно
board[r][c] = '#'
found = dfs(r, c, index + 1)
board[r][c] = char # Восстанавливают!Почему это неправильно: Следующие пути не смогут использовать клетку.
Проблема: Не дополняют числа до 32 бит.
# ❌ Неправильно
for num in nums:
bits = bin(num)[2:] # Разная длина!
# ✅ Правильно
for num in nums:
bits = format(num, '032b') # Всегда 32 битаПочему это неправильно: Разная длина битов ломает Trie.
Проблема: Не проверяют, что слово состоит минимум из 2 слов.
# ❌ Неправильно
if node.is_word:
return True # Может вернуть True для самого слова!
# ✅ Правильно
if node.is_word and count > 1:
return True # Минимум 2 словаПочему это неправильно: Слово должно состоять из других слов.
Условие: Реализуйте Trie (префиксное дерево) с методами insert, search, startsWith.
Пример:
Ввод: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Вывод: [null, null, true, false, true, null, 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Объяснение:
Сложность:
Trie эффективен для:
Оптимизации:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.