Поиск по префиксу и проверка начала строки
Добавьте метод starts_with, возвращающий true, если какое-либо вставленное слово имеет заданный префикс, и используйте его для реализации подсказок автодополнения
«Поиск по префиксу и проверка начала строки» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Сила запросов по префиксу
Главное преимущество Trie перед хеш-таблицей — эффективные запросы по префиксу. Такой запрос может определить: «сколько сохранённых слов начинается с этого префикса?», «каковы все сохранённые слова с этим префиксом?» или просто «существует ли слово с этим префиксом?». Эти запросы выполняются за O(p), где p — длина префикса, независимо от общего количества сохранённых слов, поэтому Trie идеально подходят для autocomplete и поисковых подсказок.
Метод starts_with
starts_with(prefix) возвращает значение «истина», если какое-либо сохранённое слово начинается с заданного префикса. Проходите по Trie, следуя за каждым символом префикса. Если все символы можно пройти, не встретив отсутствующего ребра, префикс существует и хотя бы одно слово с него начинается. Реализация совпадает с реализацией search, за исключением того, что после завершения прохода мы сразу возвращаем значение «истина» и не проверяем is_end.
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 starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # Falseautocomplete: поиск всех слов по префиксу
Чтобы реализовать autocomplete, пройдите до конечной вершины префикса, а затем выполните DFS или BFS от этой вершины, собирая все слова, ветвящиеся от неё. Добавьте префикс перед каждым собранным окончанием, чтобы восстановить полные слова. Операция выполняется за O(p + W), где W — общее количество символов во всех совпадающих словах.
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 autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']Возврат отсортированных предложений
Для отсортированного autocomplete проходите дочерние вершины в алфавитном порядке во время DFS, перебирая sorted(node.children.items()). Поскольку дочерние вершины хранятся в словаре, это добавляет затраты O(размер алфавита × глубина), но гарантирует результаты в лексикографическом порядке. Trie на основе массива всегда перебирает дочерние вершины в алфавитном порядке, поскольку индексы от 0 до 25 упорядочены.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')Топ-K предложений autocomplete
Для топ-K предложений по частоте добавьте к каждой вершине счётчик того, сколько раз выполнялся поиск слова, заканчивающегося в этой вершине. При сборе предложений используйте кучу максимумов размера k. Это сокращает набор результатов DFS с O(W) до O(k), не создавая все совпадения в памяти. Реальные поисковые системы объединяют проход Trie по префиксу с данными о частоте, чтобы быстро формировать релевантные предложения.
Реализация Trie для LeetCode 208
В задаче LeetCode 208 «Реализовать Trie (префиксное дерево)» требуется ровно следующее: insert(word), search(word), возвращающий логическое значение точного совпадения, и startsWith(prefix), возвращающий логическое значение совпадения по префиксу. Это каноническая реализация Trie. Помните: search требует is_end=True, а startsWith требует только существования пути префикса.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # TrueИспользование '#' как маркера конца (Trie на словаре)
Элегантный сокращённый вариант хранит Trie как вложенные словари со специальным ключом-маркером, например '#', обозначающим конец слова. Благодаря этому класс TrieNode не нужен. Такой вариант компактен и удобен на собеседованиях, но немного менее понятен, чем явные объекты TrieNode. Допустимы обе реализации; вариант со словарями быстрее написать при ограниченном времени.
Наибольший общий префикс с помощью Trie
Чтобы найти наибольший общий префикс списка строк, вставьте все строки в Trie, а затем пройдите от корня по единственному существующему пути, пока выполняются оба условия: (1) у текущей вершины ровно одна дочерняя вершина; (2) is_end имеет значение «ложь». Остановитесь, как только одно из условий перестанет выполняться. Пройденный путь и есть наибольший общий префикс.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Задача «Замена слов»
Замена слов (LeetCode 648): даны словарь корневых слов и предложение; замените каждое слово в предложении самым коротким подходящим корневым словом из словаря. Вставьте все корневые слова в Trie. Для каждого слова предложения проходите по Trie, пока не найдёте конец корневого слова, и верните это корневое слово как замену. Если ни одно корневое слово не подходит, оставьте исходное слово. Сложность составляет O(общая длина символов) вместо O(n × m) при полном переборе.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Задача «Суммирование по отображению»
Суммирование по отображению (LeetCode 677): вставляйте пары ключ–значение и возвращайте сумму всех значений, ключи которых имеют заданный префикс. Добавьте к каждому TrieNode поле val. При выполнении insert пройдите до конца ключа и установите значение; для запросов суммы пройдите до конечной вершины префикса и просуммируйте с помощью DFS все поля val ниже неё. Другой вариант — хранить накопленную сумму в каждой вершине во время вставки, чтобы выполнять запросы за O(p).
Реализация автодополнения с ограниченным числом результатов
В промышленных системах автодополнения возвращать все слова с префиксом непрактично, если ему соответствуют тысячи слов. Вместо этого во время обхода DFS используйте макс-кучу размера k: поддерживайте k слов с наивысшей оценкой среди уже найденных. Досрочно прекращайте обработку ветвей DFS, если они не могут содержать слово, входящее в первые k результатов (отсечение по верхней границе оценки). Это даёт O(p + k × log k) на один запрос с k подсказками — значительно лучше, чем сбор всех совпадений.
Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.
Итоги урока
В этом уроке вы изучили следующее: проверка наличия префикса проходит по пути префикса и возвращает True, если он существует — проверка окончания слова не требуется, автодополнение с помощью DFS собирает все слова из конечного узла префикса, добавляя символы по мере спуска, а также добавление к узлам счётчиков или значений позволяет выполнять запросы сумм и получать первые k подсказок. Далее мы добавим в префиксное дерево поиск с подстановочными символами и регулярными выражениями.
Часто задаваемые вопросы
Урок «Поиск по префиксу и проверка начала строки» бесплатный?
Да — полный текст урока «Поиск по префиксу и проверка начала строки» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Поиск по префиксу и проверка начала строки»?
Добавьте метод starts_with, возвращающий true, если какое-либо вставленное слово имеет заданный префикс, и используйте его для реализации подсказок автодополнения Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Поиск по префиксу и проверка начала строки»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Класс TrieNode: вставка и поиск
- Поиск по префиксу и проверка начала строки
- Поиск по шаблону и регулярному выражению в дереве префиксов
- Поиск слов II: дерево префиксов и перебор с возвратом на сетке