Поиск по шаблону и регулярному выражению в дереве префиксов
Поддержите сопоставление с подстановочным символом '.', переходя на всех потомков текущей глубины, и решите задачу о структуре данных для добавления и поиска слов
«Поиск по шаблону и регулярному выражению в дереве префиксов» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Задача поиска с подстановочными символами
Стандартный поиск в префиксном дереве обрабатывает точные символы. Поиск с подстановочными символами добавляет специальный символ '.', который соответствует любому одному символу. Встретив '.' во время поиска, вместо перехода к одному определённому дочернему узлу необходимо попробовать все дочерние узлы — выполнить разветвление. Это основная идея задачи LeetCode 211 «Проектирование структуры данных для добавления и поиска слов». Каждый '.' умножает число путей поиска на количество дочерних узлов на соответствующем уровне.
Рекурсивный поиск с подстановочными символами
Реализуйте поиск с подстановочными символами с помощью вспомогательной рекурсивной функции DFS. Для каждого символа шаблона: если это обычный символ, перейдите к соответствующему дочернему узлу (или верните False, если его нет); если это '.', рекурсивно обработайте все дочерние узлы и верните True, если хотя бы один вызов успешен. В конце шаблона верните node.is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(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):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # FalseЗачем использовать разветвление
При встрече '.' вызывается any(dfs(child, i+1) for child in node.children.values()). Генератор any() использует вычисление с ранним завершением — он останавливается сразу после того, как один дочерний узел возвращает True. Это позволяет избежать ненужного исследования. В худшем случае, когда весь шаблон состоит из '.', исследуются все пути — сложность составляет O(26^k), где k — количество точек, поэтому шаблоны вроде '....' становятся затратными для больших префиксных деревьев.
Итеративный поиск с подстановочными символами и очередями
В итеративном подходе используется очередь пар (node, index). Начните с (root, 0). Для каждой пары, если index == len(word) и node.is_end, верните True. В противном случае обработайте текущий символ: для '.' добавьте в очередь все дочерние узлы, а для обычного символа — только соответствующий дочерний узел. По сути, это BFS по путям в префиксном дереве.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')Анализ сложности поиска с подстановочными символами
Для шаблона без подстановочных символов поиск выполняется за O(m). Для шаблона с k подстановочными символами сложность в худшем случае составляет O(26^k × m) — она экспоненциальна по количеству подстановочных символов. На практике подстановочные символы обычно встречаются редко, а префиксное дерево имеет небольшую глубину, поэтому производительность остаётся приемлемой. Для шаблонов, полностью состоящих из подстановочных символов (например, для поиска всех слов длины k), алгоритм вырождается в полный обход префиксного дерева.
Поиск по регулярным выражениям за пределами подстановочных символов одного знака
Для расширения до полноценных регулярных выражений (например, когда '*' соответствует нулю или более символам) требуется другой подход. '*' может соответствовать любому суффиксу, поэтому при его встрече необходимо попробовать все пути префиксного дерева из текущего узла. Полнотное сопоставление с регулярными выражениями в префиксном дереве сложно — обычно для него применяются конструкции NFA/DFA. На собеседованиях стандартным вариантом считаются подстановочные символы одного знака ('.').
Сопоставление с шаблонами
Сопоставление с шаблонами с помощью '?' (любой один символ) и '*' (любая последовательность, включая пустую) можно реализовать с помощью DP. При реализации в префиксном дереве '?' соответствует разветвлению на одном уровне (как '.'), а '*' — многоуровневому DFS. Комбинированный подход с DP: dp[i][j] = True, если pattern[0..i] соответствует string[0..j]. Обычно интервьюер уточняет, какой вариант необходимо реализовать.
Практическое применение: маршрутизация IP-адресов
Префиксные деревья с подстановочными символами используются в таблицах маршрутизации IP, где '*' выступает как подстановочный символ префикса. Маршрутизатор хранит префиксы маршрутов, например '192.168.*', и сопоставляет с ними входящие адреса. Сопоставление по самому длинному префиксу (побеждает наиболее специфичный маршрут) реализуется обходом префиксного дерева на максимально возможную глубину с использованием последнего найденного совпадения. Это практическое применение операций с префиксами и подстановочными символами в префиксном дереве.
Оптимизация: отсечение бесполезных ветвей
Если у узла префиксного дерева нет дочерних узлов (это лист) и is_end = False, любой поиск, достигший этого узла, возвращает False. Во время поиска с подстановочными символами пропуск таких тупиковых узлов до рекурсивного вызова позволяет отсечь ненужные вызовы. Хранение word_count в каждом узле (общего количества слов в поддереве) позволяет пропустить всё поддерево, если ни одно слово не соответствует ограничениям на длину оставшейся части шаблона.
Полный класс WordDictionary для собеседования
Это чистый вариант класса WordDictionary, готовый для собеседования, который объединяет вставку и поиск с подстановочным символом-точкой в одном классе. Это точная реализация, ожидаемая для LeetCode 211. Рекурсивный поиск с ранним завершением краток и наглядно демонстрирует логику разветвления для интервьюеров.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # FalseИспользование setdefault для компактного префиксного дерева
dict.setdefault(key, default) возвращает значение для ключа, если ключ присутствует, иначе вставляет default и возвращает его. Использование node.setdefault(c, {}) при вставке устраняет проверку if-else: если дочернего словаря нет, он создаётся, а затем в любом случае возвращается. Благодаря этому вставка превращается в обход в одну строку: for c in word: node = node.setdefault(c, {}). Чистый и соответствующий стилю Python код.
Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.
Итоги урока
В этом уроке вы изучили следующее: подстановочный символ '.' требует разветвления по всем дочерним узлам в соответствующей позиции с использованием рекурсивного DFS, проверка любого элемента с генератором обеспечивает вычисление с ранним завершением, а также setdefault позволяет реализовать вставку в префиксное дерево одной компактной строкой. Далее мы объединим префиксное дерево и поиск с возвратом, чтобы решить задачу «Поиск слов II» — найти несколько слов одновременно на двумерной доске.
Часто задаваемые вопросы
Урок «Поиск по шаблону и регулярному выражению в дереве префиксов» бесплатный?
Да — полный текст урока «Поиск по шаблону и регулярному выражению в дереве префиксов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Поиск по шаблону и регулярному выражению в дереве префиксов»?
Поддержите сопоставление с подстановочным символом '.', переходя на всех потомков текущей глубины, и решите задачу о структуре данных для добавления и поиска слов Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Поиск по шаблону и регулярному выражению в дереве префиксов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Класс TrieNode: вставка и поиск
- Поиск по префиксу и проверка начала строки
- Поиск по шаблону и регулярному выражению в дереве префиксов
- Поиск слов II: дерево префиксов и перебор с возвратом на сетке