Regular Expression Matching и Wildcard Matching: ДП по двум строкам

Разбор задач Regular Expression Matching и Wildcard Matching: рекурсия, таблица ДП по двум строкам, переходы для точки, звёздочки и вопроса, жадное решение для wildcard и типичные ошибки.

12 мин чтенияалгоритмы · строки · динамическое программирование · python

Коротко

Regular Expression MatchingWildcard Matching
Спецсимволы. — любой символ, * — ноль или больше повторов предыдущего символа? — любой символ, * — любая последовательность, в том числе пустая
Состояниеdp[i][j] — совпадает ли префикс s[:i] с префиксом p[:j]то же самое
Время / памятьO(n⋅m)O(n \cdot m) / O(n⋅m)O(n \cdot m), сжимается до O(m)O(m)O(n⋅m)O(n \cdot m) / O(m)O(m), жадно — O(1)O(1) памяти
Главная ловушка* привязана к символу перед ней: a* — один токенпустая строка против шаблона ***

Обе задачи — про одно и то же: проверить, что вся строка s целиком подходит под шаблон p. Решаются одной схемой ДП по двум префиксам, отличаются только переходами для *. Для wildcard есть ещё жадный алгоритм с откатом к последней звёздочке.

Условия задач

Regular Expression Matching (LeetCode 10, Hard). Дана строка s из строчных латинских букв и шаблон p, в котором кроме букв встречаются . и *. Точка совпадает с любым одним символом. Звёздочка означает «ноль или больше повторений предыдущего элемента». Гарантируется, что перед каждой * стоит буква или точка. Нужно вернуть True, если шаблон покрывает строку полностью.

s = "aa",          p = "a"            → False  (не вся строка)
s = "aa",          p = "a*"           → True   (a повторена дважды)
s = "ab",          p = ".*"           → True   (любой символ сколько угодно раз)
s = "aab",         p = "c*a*b"        → True   (c ноль раз, a дважды, b)
s = "mississippi", p = "mis*is*p*."   → False

Wildcard Matching (LeetCode 44, Hard). То же самое, но шаблон в стиле масок файлов: ? — ровно один любой символ, * — любая последовательность символов, включая пустую. Здесь звёздочка самостоятельна и ни к чему не привязана.

s = "aa",    p = "*"     → True
s = "cb",    p = "?a"    → False
s = "adceb", p = "*a*b"  → True
s = "acdcb", p = "a*c?b" → False

Главное различие, которое путают на собеседованиях: в регулярках a* — это один токен «сколько-то букв a», а в wildcard * — сама по себе «что угодно».

Почему не работает простой проход

Хочется идти двумя указателями и жадно сопоставлять символы. Проблема — звёздочка. Сколько символов она должна съесть? Возьмём s = "aaa", p = "a*a". Если a* жадно съест все три a, на последний символ шаблона ничего не останется, и ответ будет ложно отрицательным. Правильно — съесть две.

Значит, в каждой звёздочке есть выбор, и нужно перебирать варианты. Перебор с повторяющимися подзадачами — классический сигнал к динамическому программированию (если тема новая, начните с основ ДП).

Regular Expression Matching: рекурсия

Сформулируем задачу через суффиксы: совпадает ли s[i:] с p[j:].

  • Если шаблон кончился, строка тоже должна кончиться.
  • first — совпадает ли первый символ: строка не пуста и p[j] равен s[i] или точке.
  • Если за p[j] идёт *, есть два варианта:
    • пропустить токен x* целиком (ноль повторов) — перейти к p[j+2:];
    • если первый символ совпал, съесть его и остаться на том же токене — перейти к s[i+1:], p[j:].
  • Иначе просто сдвинуться на один символ в обеих строках, если первый совпал.
def is_match_rec(s: str, p: str) -> bool: if not p: return not s first = bool(s) and p[0] in (s[0], '.') if len(p) >= 2 and p[1] == '*': return is_match_rec(s, p[2:]) or (first and is_match_rec(s[1:], p)) return first and is_match_rec(s[1:], p[1:])

Код правильный, но экспоненциальный: на строке aaaaaaaaaaaaab и шаблоне a*a*a*a*a*c одни и те же пары суффиксов разбираются заново. Пар (i, j) всего (n+1)(m+1)(n+1)(m+1), поэтому достаточно их запомнить — это мемоизация.

from functools import lru_cache def is_match_memo(s: str, p: str) -> bool: @lru_cache(maxsize=None) def dp(i: int, j: int) -> bool: if j == len(p): return i == len(s) first = i < len(s) and p[j] in (s[i], '.') if j + 1 < len(p) and p[j + 1] == '*': return dp(i, j + 2) or (first and dp(i + 1, j)) return first and dp(i + 1, j + 1) return dp(0, 0)

На собеседовании такой вариант уже засчитывают как оптимальный по асимптотике: O(n⋅m)O(n \cdot m) состояний, каждое за O(1)O(1). Но часто просят итеративную таблицу — разберём её.

Regular Expression Matching: таблица ДП

Переходим к префиксам. dp[i][j] — совпадают ли первые i символов строки с первыми j символами шаблона. Ответ — dp[n][m]. Удобно сдвинуть индексы на единицу: текущий символ строки — s[i-1], шаблона — p[j-1].

База

  • dp[0][0] = True: пустая строка совпадает с пустым шаблоном.
  • dp[i][0] = False при i > 0: непустую строку пустой шаблон не покрывает.
  • dp[0][j]: пустая строка совпадает с шаблоном, только если он целиком состоит из токенов вида x*, каждый из которых взят ноль раз. Поэтому dp[0][j] = dp[0][j-2], если p[j-1] == '*'.

Переходы

Обычный символ или точка. Если p[j-1] равен s[i-1] или это ., символы съедаются парой:

dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]

Звёздочка. p[j-1] == '*', токен — p[j-2]*. Два случая:

  1. Ноль повторений: выкидываем токен из шаблона, строку не трогаем — dp[i][j-2].
  2. Ещё одно повторение: если p[j-2] совпадает с s[i-1] (или это точка), последний символ строки съедается токеном, а сам токен остаётся доступным для предыдущих символов — dp[i-1][j].

dp[i][j]=dp[i][j−2]∨(match(si−1,pj−2)∧dp[i−1][j])dp[i][j] = dp[i][j-2] \lor \big(\text{match}(s_{i-1}, p_{j-2}) \land dp[i-1][j]\big)

Второй случай — суть задачи. Мы не перебираем явно «съесть 1, 2, 3 символа»: ссылка на dp[i-1][j] сама раскручивается вверх по таблице, пока символы подходят. Тот же приём, что в неограниченном рюкзаке, где предмет можно брать повторно.

def is_match(s: str, p: str) -> bool: n, m = len(s), len(p) dp = [[False] * (m + 1) for _ in range(n + 1)] dp[0][0] = True for j in range(2, m + 1): if p[j - 1] == '*': dp[0][j] = dp[0][j - 2] for i in range(1, n + 1): for j in range(1, m + 1): if p[j - 1] == '*': dp[i][j] = dp[i][j - 2] # ноль повторений if p[j - 2] in (s[i - 1], '.'): dp[i][j] = dp[i][j] or dp[i - 1][j] # ещё одно elif p[j - 1] in (s[i - 1], '.'): dp[i][j] = dp[i - 1][j - 1] return dp[n][m]

Разбор на примере

s = "aab", p = "c*a*b". Строки таблицы — префиксы s, столбцы — префиксы p. T — совпадает, · — нет.

""c*a*b
""T·T·T·
a···TT·
aa····T·
aab·····T

Что происходит:

  • Первая строка: c* и c*a* могут быть пустыми, поэтому T в столбцах звёздочек.
  • dp[1][3] (a против c*a): символы совпали, берём dp[0][2] = T.
  • dp[1][4] (a против c*a*): ноль повторений даёт dp[1][2] = ·, но a совпадает с токеном a*, а dp[0][4] = T. Итог T.
  • dp[2][4] (aa против c*a*): снова «ещё одно повторение», dp[1][4] = T.
  • dp[3][5] (aab против c*a*b): b == b, берём dp[2][4] = T. Ответ True.

Видно, как звёздочка «протягивает» T вниз по своему столбцу, пока символы строки подходят под токен.

Память

Каждая строка таблицы зависит только от себя (dp[i][j-2]) и предыдущей (dp[i-1][j], dp[i-1][j-1]). Значит, хватает двух массивов длины m + 1 — O(m)O(m) памяти. На интервью это хороший follow-up, но сначала напишите полную таблицу: в ней проще не ошибиться.

Wildcard Matching: та же таблица

Состояние то же: dp[i][j] — совпадает ли s[:i] с p[:j].

  • ? или совпавшая буква: dp[i][j] = dp[i-1][j-1].
  • *: либо звёздочка пустая — dp[i][j-1], либо она съедает символ s[i-1] и остаётся жить дальше — dp[i-1][j].

dp[i][j]=dp[i][j−1]∨dp[i−1][j]dp[i][j] = dp[i][j-1] \lor dp[i-1][j]

Отличие от регулярок в двух местах. Пропуск звёздочки — это j-1, а не j-2: она самостоятельный токен. И при поглощении символа ничего проверять не надо — * подходит под что угодно.

База: dp[0][j] истинно, только если p[:j] состоит из одних звёздочек.

def wildcard_dp(s: str, p: str) -> bool: n, m = len(s), len(p) prev = [False] * (m + 1) prev[0] = True for j in range(1, m + 1): prev[j] = prev[j - 1] and p[j - 1] == '*' for i in range(1, n + 1): cur = [False] * (m + 1) for j in range(1, m + 1): if p[j - 1] == '*': cur[j] = cur[j - 1] or prev[j] elif p[j - 1] in (s[i - 1], '?'): cur[j] = prev[j - 1] prev = cur return prev[m]

Здесь сразу версия на двух строках: prev — предыдущая строка таблицы, cur — текущая. Обратите внимание, что cur[0] остаётся False — непустой префикс строки пустым шаблоном не покрыть.

Wildcard Matching: жадное решение

У wildcard есть решение за O(1)O(1) памяти, которого у регулярок нет. Идея: идём двумя указателями и запоминаем последнюю встреченную звёздочку. Сначала считаем, что она пустая. Если дальше случился конфликт — откатываемся к ней и даём ей съесть на один символ больше.

def wildcard_greedy(s: str, p: str) -> bool: i = j = 0 star = -1 # позиция последней '*' в шаблоне mark = 0 # позиция в s, с которой эта '*' начала поглощать while i < len(s): if j < len(p) and p[j] in (s[i], '?'): i += 1 j += 1 elif j < len(p) and p[j] == '*': star, mark = j, i j += 1 elif star != -1: mark += 1 i, j = mark, star + 1 else: return False while j < len(p) and p[j] == '*': j += 1 return j == len(p)

Трассировка для s = "adceb", p = "*a*b":

Шагi (s)j (p)Действие
10 a0 *запомнили звезду: star=0, mark=0
20 a1 aсовпало
31 d2 *новая звезда: star=2, mark=1
41 d3 bконфликт → звезда съедает d, i=2
52 c3 bконфликт → звезда съедает c, i=3
63 e3 bконфликт → звезда съедает e, i=4
74 b3 bсовпало, строка кончилась, шаблон тоже → True

Почему откат только к последней звёздочке

Это ключевой вопрос, который задают после жадного кода. Пусть шаблон разбит звёздочками на куски: *A*B*C. Каждый кусок без звёздочек надо найти в строке по порядку, не пересекаясь. Если кусок A уже найден в самой левой возможной позиции, сдвигать его правее бессмысленно: это только сокращает остаток строки для B и C. Поэтому когда что-то не сошлось, менять решение для более ранних звёздочек незачем — достаточно двигать последнюю.

В регулярках это не работает: a* поглощает только буквы a, и выбор числа повторов одного токена влияет на то, что смогут сделать следующие. Жадности там места нет, нужна полноценная ДП.

Сложность жадного решения

Память O(1)O(1). Время в худшем случае O(n⋅m)O(n \cdot m): на каждом откате указатель шаблона может пройти кусок заново. Например, s = "aaaa...a", p = "*aaa...ab". На практике жадный вариант заметно быстрее таблицы, потому что откатывается редко.

Сравнение подходов

ПодходВремяПамятьГде применим
Наивная рекурсияэкспонентаO(n+m)O(n + m) стектолько как первый набросок
МемоизацияO(n⋅m)O(n \cdot m)O(n⋅m)O(n \cdot m)обе задачи
Таблица ДПO(n⋅m)O(n \cdot m)O(n⋅m)O(n \cdot m) или O(m)O(m)обе задачи
Жадный с откатомO(n⋅m)O(n \cdot m) в худшемO(1)O(1)только wildcard

Как это связано с настоящими регулярками

Наивная рекурсия из начала статьи — это, по сути, то, как работают движки с бэктрекингом: они пробуют вариант, а при неудаче откатываются и пробуют следующий. Так устроены re в Python, регулярки в JavaScript, Java и PCRE. Поддерживать обратные ссылки и lookahead так проще, но плата за это — экспоненциальное время на неудачных шаблонах.

Классический пример — шаблон (a+)+b на строке из тридцати букв a без b в конце. Движок перебирает все способы разбить a между внутренним и внешним плюсом, а их экспоненциально много. Это называется катастрофическим бэктрекингом, а атака, которая подсовывает серверу такую строку, — ReDoS. В июле 2019 года именно неудачная регулярка в правилах WAF загрузила процессоры Cloudflare на все сто процентов и положила значительную часть их сети почти на полчаса.

Движки вроде RE2 (Google) и regex в Rust и Go идут другим путём: строят автомат и гарантируют линейное время от длины строки. Ценой отказа от обратных ссылок. Наша таблица ДП по духу ближе к ним: мы не перебираем пути, а для каждого префикса строки помним множество позиций шаблона, где можно оказаться. Столбец j с True в строке i — это и есть «состояние автомата j достижимо после чтения i символов».

Рассказать об этом на собеседовании необязательно, но если интервьюер спросит «а зачем вообще ДП, если есть re?», это хороший ответ.

Вариации задачи

Интервьюеры любят слегка менять условие, чтобы проверить, понимаете ли вы переходы, а не помните код.

Добавить +. «Один или больше повторов». Самый простой путь — переписать шаблон: x+ эквивалентно xx*. Если переписывать нельзя, переход такой же, как у звёздочки, только без варианта «ноль раз»: символ строки обязан совпасть с токеном, и дальше либо остаёмся на токене, либо переходим к следующему.

Добавить ? в регулярку. «Ноль или один раз»: dp[i][j] = dp[i][j-2] or (match and dp[i-1][j-2]). Отличие от звёздочки — после поглощения символа токен больше недоступен.

Искать совпадение не со всей строкой, а с подстрокой. Достаточно мысленно дописать .* в начало и в конец шаблона. В таблице это значит, что первый столбец становится целиком True, а ответ — «есть ли True в последнем столбце».

Посчитать число способов сопоставления. Вместо or складываем, вместо True/False храним числа. Структура таблицы не меняется — это частая проверка, что вы понимаете ДП, а не выучили конкретную формулу.

Типичные ошибки

Обрабатывать * в регулярке как отдельный символ. a* — единый токен. Если в переходе для звёздочки смотреть на p[j-1] вместо p[j-2], всё ломается. Проверяйте символ перед звёздочкой.

Забыть инициализацию первой строки. Без dp[0][j] = dp[0][j-2] пустая строка не совпадёт с a*b*, а строка aab — с c*a*b, потому что T для префикса c* не появится.

Путать j-2 и j-1. В регулярках пропуск звёздочки — j-2 (выкидываем символ и звёздочку), в wildcard — j-1.

Проверять совпадение при поглощении в wildcard. * в wildcard съедает что угодно, условие p[j-2] == s[i-1] здесь лишнее и неверное.

Решить через re.fullmatch. На LeetCode пройдёт, на собеседовании — нет: задача ровно в том, чтобы написать сопоставление самому.

Принимать частичное совпадение. "aa" против "a" — False. Ответ — dp[n][m], а не «где-то в таблице есть T».

Как проверить себя

Перед тем как сдавать решение, полезно сравнить его с эталоном на случайных тестах. Для регулярок эталон — модуль re, для wildcard — fnmatch.fnmatchcase (на алфавите без [):

import fnmatch import random import re for _ in range(20000): s = ''.join(random.choice('ab') for _ in range(random.randint(0, 7))) p = '' for _ in range(random.randint(0, 6)): p += random.choice('ab.') if random.random() < 0.4: p += '*' assert is_match(s, p) == (re.fullmatch(p, s) is not None), (s, p) q = ''.join(random.choice('ab?*') for _ in range(random.randint(0, 7))) expected = fnmatch.fnmatchcase(s, q) assert wildcard_dp(s, q) == wildcard_greedy(s, q) == expected, (s, q) print('ok')

Такой стресс-тест за секунду ловит ошибки в базе и в индексах, которые глазами не видно.

На собеседовании

Обе задачи — частые Hard из подборок крупных компаний. Типичный ход разговора:

  1. Уточнить условие: шаблон должен покрыть всю строку; что именно значит *; может ли шаблон начинаться со звёздочки.
  2. Написать рекурсию, показать, где перебор.
  3. Добавить мемоизацию или перейти к таблице, назвать O(n⋅m)O(n \cdot m).
  4. Прогнать вручную маленький пример вроде aab / c*a*b.
  5. Follow-up: память O(m)O(m), а для wildcard — жадное решение и объяснение, почему откат только к последней звезде.

Если рекурсия уже понятна, таблица выводится механически: каждое return из рекурсии превращается в формулу перехода. Это тот же путь, что в расстоянии Левенштейна и наибольшей общей подпоследовательности — ДП по двум строкам с состоянием «префикс первой × префикс второй». Ещё одна задача с похожей структурой — Word Break, где строку тоже надо покрыть целиком.

Потренироваться в спокойной обстановке

Все задачи