Разбор задачи «Regular Expression Matching»

В этой статье я разберу решение задачи сопоставления строки шаблону с регулярным выражением, которая предлагается сайтом LeetCode под номером 10. Постановка. Даны строка и шаблон , реализующий регулярное выражение с поддержкой специальных символов и , где: сопоставляется с любым символом входящей строки, совместно с предыдущим символом шаблона сопоставляется с подстрокой из нуля или более таких же символов во входящей строке. Необходимо ответить на вопрос, соответствует ли представленная строка шаблону или нет. При этом соответствие должно охватывать всю входную строку, а не только её часть. Пример 1. Вход: , Выход: Объяснение: шаблон не совпадает со всей строкой . Пример 2. Вход: , Выход: Объяснение: означает ноль или более предшествующих элементов , таким образом, при повторении , получается . Пример 3. Вход: , Выход: Объяснение: означает последовательность из нуля или более любых символов. Ограничения: содержит только буквы латинского алфавита в нижнем регистре. содержит только буквы латинского алфавита в нижнем регистре. гарантируется, что для каждого символа в шаблоне всегда присутствует предыдущий символ, совместно с которым используется. Метод. Существует несколько методик проверки соответствия строки регулярному выражению. Традиционно эта задача решается с помощью недетерминированного конечного автомата (Nondeterministic Finite Automaton, NFA), в который компилируется регулярное выражение. Автомат читает строку символов и использует её как инструкцию для изменения своего состояния, чтобы в конце концов ответить на вопрос, соответствует ли входящая строка исходному шаблону или нет. Однако, LeetCode любезно подсказывает нам, что в данном случае лучше применить динамическое программирование. Воспользуемся этим советом. Введем функцию соответствия , которая принимает на вход строку и шаблон , а возвращает либо , если строка соответствует шаблону, либо в противном случае. Нам необходимо придумать реализацию этой функции. Для этого мы проанализируем, как должна работать функция соответствия на примере нескольких частных случаев, и воспользуемся "реверсивным инжинирингом", чтобы попытаться воссоздать её реализацию. Рекурсия. Пусть и . При использовании динамического программирования первое, что необходимо сделать, это разбить исходную задачу на более мелкие подзадачи. Пусть - строка, состоящая из первых символов строки , - шаблон, состоящий из первых символов шаблона , а - результат сопоставления строки шаблону . Тогда получим такие значения и : Вычислим значения функции для каждой ячейки представленной таблицы. Поскольку пустая строка и пустой шаблон эквивалентны, следовательно . Очевидно, любая непустая строка не сопоставима с пустым шаблоном, как и любой непустой шаблон без специальных символов не сопоставим с пустой строкой, следовательно: В итоге получаем следующую таблицу: В нашем примере шаблон не использует специальные символы, поэтому соответствие строки шаблону определяется простым отношением эквивалентности. Теперь попробуем выразить решение через решения более мелких подзадач , таких, что и . Заметьте, что , так как выполняется два условия: во-первых, последний символ строки эквивалентен последнему символу шаблона , и, во-вторых, подстрока строки без её последнего символа соответствует шаблону без его последнего символа. Пусть - это последний символ строки , а - это последний символ шаблона , тогда обобщив полученную выше формулу для всей таблицы, получим: Таким образом, чтобы вычислить значение необходимо знать значение , чтобы вычислить значение , необходимо знать значение , а значение , необходимое для вычисления уже известно: , это базовый случай для рекурсии, которую мы вывели. Универсальный символ. В предыдущей части мы рассмотрели тривиальный случай, когда в шаблоне не было никаких специальных символов. Теперь попробуем сопоставить строку с шаблоном . В шаблоне появился символ "точка", соответствующий любому символу строки . Его также называют подстановочным или универсальным символом. Разобьём строку и шаблон на подзадачи и заполним таблицу соответствия по аналогии с предыдущим примером. Как видите, в таблице практически ничего не изменилось. Хотя в шаблоне теперь вместо символа стоит символ , но на результат проверки соответствия это никак не повлияло, ведь универсальный символ шаблона можно сопоставить с любым символом строки , в том числе с символом . В предыдущей части мы вывели рекурсивную формулу для вычисления функции соответствия: . Введем функцию соответствия последнего символа строки последнему символу шаблона: , то есть имеет значение тогда и только тогда, когда либо последний символ строки эквивалентен последнему символу шаблона : , где - последний символ строки , а - последний символ шаблона , либо последний символ шаблона является универсальным символом, то есть . Тогда рекурсивная формула соответствия примет следующий вид: Звезда Клини. По условию задачи в регулярном выражении может присутствовать символ "звездочка", также известный как звезда Клини. Он играет роль итератора для предыдущего символа шаблона. Если после какого-либо символа шаблона следует звезда Клини, то этой паре, символ и звезда, можно поставить в соответствие строку длины ноль или более из таких же символов. Например, шаблон соответствует строке , строке , строке и даже пустой строке . Cопоставим строку с шаблоном . Функция сопоставления строк с шаблонами без звезды Клини вычисляется также как и в предыдущих примерах. Изменения появляются при сопоставлении строк с шаблоном : Почему строка соответствует шаблону ? Причина в звезде Клини. Шаблону можно поставить в соответствие строку, состоящую из символов любой длины в том числе и нулевой. Это значит, мы можем сопоставить выражение с пустой подстрокой в строке . Представим строку как конкатенацию строки и пустой строки: . Шаблон соответствует этой конкатенации тогда и только тогда, когда пустая строка сопоставляется с последними двумя символами этого шаблона, то есть , а оставшаяся часть строки соответствует оставшейся части шаблона. Почему строка соответствует шаблону ? Причина снова в звезде Клини. Однако, на этот раз шаблон сопоставляется не с пустой строкой, а со строкой . Чтобы сопоставление строки с шаблоном было успешным, необходимо выполнение двух условий. Во-первых, последний символ строки должен соответствовать предпоследнему символу шаблона, тому символу, который итерируется звездой Клини. И, во-вторых, оставшаяся часть строки, без последнего символа, тоже должна соответствовать текущему шаблону. Заметьте, на этот раз мы не удаляем из шаблона последние два символа , они нам ещё понадобятся для вычисления функции соответствия на шаге . Также, обратите внимание, что последний символ строки не обязан быть эквивалентным предпоследнему символу шаблона, он должен соответствовать ему. В шаблоне может быть универсальный символ, кодируемый "точкой". Поэтому последний символ строки соответствует предпоследнему символу шаблона тогда и только тогда, когда выполняется хотя бы одно условие: либо эти символы эквивалентны друг другу, либо символ шаблона является универсальным символом. Мы видим, что формулы и различаются. В первом случае мы получили соответствие, когда полностью выкинули из шаблона выражение со звездой Клини. Во втором случае, последний символ строки оказался эквивалентен операнду звезды Клини (предпоследнему символу шаблона), что позволило выкинуть из строки этот последний символ и сопоставить шаблон с её оставшейся частью. Чтобы обобщить формулу соответствия используем дизъюнкцию (логическое ИЛИ) полученных выражений. Объединив формулу для шаблонов без звезды Клини и формулу для шаблонов со звездой Клини, получим следующую реализацию функции соответствия: , если , если Заметьте, формула "потеряла" базовый случай , который мы применяли в примерах с шаблонами без звезды Клини. Действительно, появление этого специального символа означает, что пустая строка теперь может соответствовать не только пустому шаблону. Рассмотрим сопоставление пустой строки с шаблоном . Разобьем шаблон на фрагменты , , , и . Пустая строка соответствует пустому шаблону . Однако, если шаблон указывает, что строка должна содержать хотя бы один символ, то соответствие нарушается . С другой стороны, звезда Клини в шаблоне говорит нам, что строка может содержать любое количество символов в том числе и ноль. Это значит, что пустая строка снова может быть сопоставлена с таким шаблоном . Шаблоны и повторяют ситуацию: Если шаблон заканчивается на звезду Клини, то работает формула , а в противном случае применяется базовый случай . В итоге получаем следующую формулу для вычисления функции соответствия: , если , если , если , если Сложность. Мы разобрали три случая сопоставления строки шаблону : В первых двух примерах функция соответствия была успешно вычислена по формуле . В ней рекурсивный вызов функции происходит всего один раз. Следовательно количество операций, которые необходимо выполнить для проверки соответствия, пропорционален длине строки. Это означает линейную сложность , рекурсивного алгоритма проверки. Однако, добавление в шаблон звезды Клини, резко меняет ситуацию. Чтобы проверить соответствие шаблону, последним символом которого является звезда Клини, мы применили формулу . В ней для вычисления значения в худшем случае придется выполнить два рекурсивных вызова функции соответствия: и . Это обстоятельство сразу поднимает сложность рекурсивного алгоритма до экспоненциальной . Динамическое программирование предлагает сохранять вычисленные значения и при необходимости использовать их для последующих расчетов. Это позволяет избежать повторных вычислений функции соответствия с одними и теми же аргументами. Такой прием называется мемоизацией. Например, на рисунке 10 при проверке соответствия строки шаблону мы начинаем вычисления с вызова функции , она рекурсивно вызывает функцию , которая в зависимости от реализации может вызвать сначала функцию и, получив , вызвать , либо сразу вызвать , тогда рекурсивный вызов не потребуется, но в такой реализации ветвление произойдет при вызове . Сначала будет вызвана функция , она вернет , и нам придется выполнить вызов , который в свою очередь вызывает , останавливая рекурсию базовым случаем . Применяя мемоизацию, каждый раз, когда мы получаем конкретное значение функции соответствия или , нам необходимо его запомнить. А каждый раз, когда мы вызываем функцию соответствия , нам необходимо сразу же вернуть её значение, если оно было рассчитано ранее. Это сводит сложность повторного вычисления к . Поскольку функция соответствия параметризирована двумя индексами, то для хранения вычисленных значений удобно использовать двумерный массив. Какой размерности он должен быть? Если строка содержит символов, а шаблон состоит из символов, то максимальное значение индекса равно , а максимальное значение индекса равно . Поскольку минимальное значение индексов и равно , то для хранения промежуточных результатов нам потребуется матрица размера Это значит, что для вычисления функции соответствия с применением мемоизации мы должны выполнить операций. Реализация. Мемоизацию можно использовать, когда глубина рекурсии не слишком велика. Если длина строки или шаблона окажется очень большой, это может привести к переполнению стека при рекурсивном вызове функции сопоставления. Что если вообще избавиться от рекурсивных вызовов? Вычислим сначала функцию соответствия для пустой строки и пустого шаблона. Затем добавим к пустой строке один символ и проверим соответствие строки из одного символа с пустым шаблоном. Добавим к строке следующий символ и проверим соответствие строки из двух символов с пустым шаблоном. И так далее вплоть до проверки соответствия исходной строки пустому шаблону. На самом деле, нам даже не придется ничего проверять. Сейчас мы просто рассмотрели базовый случай рекурсии в формуле функции соответствия: Сохраним эти значения в массив размера , где - длина строки, а - длина шаблона. int n = string.length(), m = pattern.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int i = 1; i <= n; i++) { dp[i][0] = false; } Теперь вычислим значения функции соответствия для пустой строки и шаблона, состоящего только из первого символа исходного шаблона. Для этого нам необходимо воспользоваться второй частью базового случая рекурсии из формулы соответствия: , если , если и ограничением из постановки задачи: гарантируется, что для каждого символа в шаблоне всегда присутствует предыдущий символ, совместно с которым используется. Поскольку в шаблоне только один символ, он не может быть звездой Клини, значит Однако, при вычислении функции соответствия для пустой строки и первых двух символов исходного шаблона, фокус с ограничением из постановки уже не сработает. Нам придется сравнить последний символ шаблона с символом звезды Клини. Создадим для этой операции специальный метод. private boolean isKleeneStar(char c) { return c == '*'; } Если проверка на звезду Клини успешна, то вместо того, чтобы рекурсивно вызвать функцию соответствия , мы просто обратимся к значению этой функции, которое было получено на предыдущем шаге for (int j = 1; j <= m; j++) { char patternChar = pattern.charAt(j - 1); if (isKleeneStar(patternChar)) { dp[0][j] = dp[0][j - 2]; } else { dp[0][j] = false; } } В итоге получим код, который вычисляет и запоминает значения функции сопоставления пустой строки со всеми вариантами шаблона: , и значения функции сопоставления всех вариантов строки с пустым шаблоном: . int n = string.length(), m = pattern.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int i = 1; i <= n; i++) { dp[i][0] = false; } for (int j = 1; j <= m; j++) { char patternChar = pattern.charAt(j - 1); if (isKleeneStar(patternChar)) { dp[0][j] = dp[0][j - 2]; } else { dp[0][j] = false; } } Теперь обратимся к спецификации языка Java, чтобы понять, что этот фрагмент кода, на самом деле, содержит довольно много лишних операций. Every variable in a program must have a value before its value is used: Each class variable, instance variable, or array component is initialized with a default value when it is created (§15.9, §15.10.2): For type boolean , the default value isfalse . Это значит, что при создании массива все его элементы уже имею значение false . Нет необходимости присваивать это значение повторно, достаточно изменить только те элементы массива, значение которых должно быть true . int n = string.length(), m = pattern.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int j = 2; j <= m; j++) { char patternChar = pattern.charAt(j - 1); if (isKleeneStar(patternChar)) { dp[0][j] = dp[0][j - 2]; } } Когда решения базовых подзадач и уже известны, их нужно использовать для вычисления более крупных задач: , если , если Такой подход, когда мы начинаем с решения мелких подзадач, а затем используем их для решения крупных подзадач, постепенно поднимая их сложность, чтобы в конечном итоге решить главную задачу, называется восходящим, и также известен как табуляция. В английской литературе его называют bottom-up подходом, в противовес мемоизации, которая называется top-down или нисходящим, подходом, и отличается от восходящего тем, что мы сразу начинаем решать главную задачу и рекурсивно опускаемся к решению более мелких подзадач, результаты которых запоминаем, чтобы впоследствии не вычислять их повторно. Мемоизация и табуляция являются двумя способами реализации методики динамического программирования на практике. Создадим метод, который вычисляет соответствие последнего символа строки последнему символу шаблона: private boolean isMatch(char sc, char pc) { return sc == pc || pc == '.'; } Тогда код, который решает остальные задачи: , если , если выглядит следующим образом: for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) { char patternChar = pattern.charAt(j - 1); if (isKleeneStar(patternChar)) { dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && isMatch(string.charAt(i - 1), pattern.charAt(j - 2))); } else { dp[i][j] = dp[i - 1][j - 1] && isMatch(string.charAt(i - 1), patternChar); } } } Как вы могли заметить, индексация при получении последнего символа строки и шаблона смещена на единицу в меньшую сторону: Это связано с тем, что в Java адресация символов строки начинается с нуля, а в нашей формуле нулевой индекс строки или шаблона означает отсутствие в них каких-либо символов. В итоге получим окончательную реализацию функции сопоставления: public class Solution { public boolean isMatch(String string, String pattern) { int n = string.length(), m = pattern.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int j = 2; j <= m; j++) { char patternChar = pattern.charAt(j - 1); if (isKleeneStar(patternChar)) { dp[0][j] = dp[0][j - 2]; } } for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) { char patternChar = pattern.charAt(j - 1); if (isKleeneStar(patternChar)) { dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && isMatch(string.charAt(i - 1), pattern.charAt(j - 2))); } else { dp[i][j] = dp[i - 1][j - 1] && isMatch(string.charAt(i - 1), patternChar); } } } return dp[n][m]; } private boolean isKleeneStar(char c) { return c == '*'; } private boolean isMatch(char sc, char pc) { return sc == pc || pc == '.'; } } Заключение. В этой статье мы разобрали, как проверить соответствие строки шаблону с регулярным выражением. Мы выяснили, что если бы в шаблоне не использовалась звезда Клини, то рекурсивный алгоритм проверки был бы очень простым и занимал линейное время, а звезда Клини сильно усложняет рекурсивную проверку, повышая её сложность до экспоненциальной. С помощью мемоизации нам удалось уменьшить сложность рекурсивного алгоритма до полиномиальной. Чтобы не допустить переполнения стека при выполнении рекурсивных вызовов, мы реализовали алгоритм проверки с помощью табуляции. Мы выяснили, что табуляция и мемоизация – это два способа имплементации парадигмы динамического программирования. В итоге, возможно, мы пришли к выводу, что решить подобную задачу на собеседовании, которое длится 60 минут, практически не реально.