Regular Expression Matching

Q: Какова временная сложность сопоставления с регулярным выражением?

Решение с таблицей работает за время O(n × m) , где n — длина s , а m — длина p , поскольку каждая ячейка считывает не более двух других. Для полной таблицы требуется O(n × m) памяти, а для двух строк — O(m) . Простая рекурсия может работать экспоненциальное время на шаблонах с большим количеством звёздочек.

Q: Почему ячейка со звёздочкой считывает ячейку сверху, а не по диагонали?

Ячейка выше, dp[i-1][j] , содержит тот же шаблон, но строка s на одну букву короче, а звёздочка всё ещё в нём. Поэтому после того, как звёздочка поглотит s[i-1] , она может поглотить и s[i-2] , и так далее вверх по столбцу. Ячейка по диагонали dp[i-1][j-2] удаляет звёздочку после одной буквы, что позволяет использовать ровно одну копию, а не любое количество.

СложноДинамическое программирование Рекурсия

+10

Дана строка s и шаблон p. В шаблоне буква соответствует такой же букве, точка . соответствует любой одной букве, а звёздочка * означает ноль или более повторений элемента, стоящего непосредственно перед ней, которым является буква или точка. Верните true, если шаблон соответствует всей строке s, а не только её части, и false в противном случае.

Функция

isMatch(s: string, p: string) → boolean

sstring: строка для поиска совпадения, только строчные буквы
pstring: шаблон из букв, точек и звёздочек
Возвращаетboolean: true, если p соответствует всему s, иначе false

Ограничения

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s содержит только строчные буквы английского алфавита.
p содержит только строчные английские буквы, . и *.
Каждая * следует за буквой или ., поэтому p никогда не начинается с * и в нём никогда не бывает двух звёзд подряд.

Примеры

Ввод: s = "moon"p = "mo*n"
Вывод: true
Пояснение: o* захватывает обе буквы o, поэтому m, o* и n точно составляют слово moon.

Ввод: s = "tree"p = "t.e"
Вывод: false
Пояснение: t.e соответствует только строкам из трёх букв: t, любая буква, затем e. Оно соответствует tre в начале tree, но последняя e остаётся, а совпадение должно охватывать всю строку s.

Ввод: s = "sky"p = "z*s.*y"
Вывод: true
Пояснение: z* означает ноль повторений z, s соответствует s, .* соответствует k, а y соответствует y. Буква со звёздочкой может обозначать отсутствие символа, поэтому z, которого нет в sky, ничего не стоит.

+29 скрытых тестов при отправке

Дополнительный вопрос

Можешь также добавить поддержку + — одного или нескольких экземпляров предшествующего ему элемента, используя ту же таблицу?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Сопоставление слева с помощью рекурсии

Верно, но не успевает на самых больших тестах

Идея

Пусть match(i, j) определяет, совпадает ли суффикс s[i:] с суффиксом p[j:]. Если шаблон закончился, он совпадает, только если строка тоже закончилась. В противном случае вычислим first: символ s[i] существует, и p[j] — это этот символ или точка.

Теперь посмотрим на один символ вперёд. Если p[j+1] — звёздочка, p[j]* — это одна единица с двумя возможными действиями. Она может взять ноль копий: пропустить оба символа с помощью match(i, j+2). Или, если условие first выполняется, она может взять одну копию: поглотить s[i] и остаться на той же единице с помощью match(i+1, j), готовая взять ещё одну. Оставаясь на j, звёздочка может обрабатывать любое количество букв, по одной за раз. Без звёздочки p[j] должен точно совпадать с одной буквой: first and match(i+1, j+1).

Это медленно, потому что каждая звёздочка делит поиск на две ветви, а ошибка часто обнаруживается только в самом конце. Возьмём 30 букв a и десять копий a*, а затем b. Рекурсия пробует каждый способ распределить часть или все 30 букв a между десятью звёздочками — около 8.5 × 10^8 способов — и выполняет около 2 × 10^9 вызовов, прежде чем сможет вернуть false. В больших тестах 1000 букв. При этом существует всего (n+1) × (m+1) различных пар (i, j).

Алгоритм

Запишите match(i, j) для суффиксов, начинающихся с i и j.
Если j находится за концом p, верните, находится ли i за концом s.
Установите first в значение, указывающее, существует ли s[i] и равно ли p[j] значению s[i] или точке.
Если p[j+1] — звёздочка, верните match(i, j+2) или first and match(i+1, j).
В противном случае верните first and match(i+1, j+1). Ответ — match(0, 0).

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

Заполните таблицу префиксов

Идея

Состояние. Пусть dp[i][j] показывает, совпадают ли первые i букв s с первыми j символами p. Индекс 0 соответствует пустому префиксу.

Базовая строка и столбец. dp[0][0] равно true: пустой шаблон совпадает с пустой строкой. Ниже в столбце 0 стоят false, потому что пустой шаблон не может совпасть с буквой. Строка 0 — более хитрый случай: префикс шаблона совпадает с пустой строкой, только если каждый его элемент отмечен звёздочкой, например z* или a*b*. Поэтому dp[0][j] равно true, когда p[j-1] — звёздочка, а dp[0][j-2] равно true.

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

Вот таблица для sky и z*s.*y со столбцами, соответствующими префиксам "", z, z*, z*s, z*s., z*s.*, z*s.*y (T означает true, F — false). Строка "" — это [T, F, T, F, F, F, F]: пустым может быть только z*. Строка s — это [F, F, F, T, F, T, F]: s совпадает с s, когда z* над ним пуст, по диагонали, а .* затем использует ноль повторений. Строка sk — это [F, F, F, F, T, T, F]: ячейка для z*s.* получает true от ещё одного повторения — точка поглощает k, и мы читаем значение T прямо над ней. Строка sky — это [F, F, F, F, F, T, T]: звёздочка после точки таким же образом поглощает y, ещё одним шагом вверх по столбцу, а затем y совпадает с y по диагонали. Последняя ячейка — true.

Каждая ячейка использует строку выше или ячейки слева, поэтому при заполнении строка за строкой, слева направо, нужные значения уже готовы. Всего это (n+1) × (m+1) ячеек — около 10^6 для самых больших тестов, при постоянном количестве операций на каждую.

Алгоритм

Создай таблицу dp из (n+1) × (m+1) значений false и установи dp[0][0] в true.
Для j от 2 до m установи dp[0][j] в true, если p[j-1] — звёздочка и dp[0][j-2] равно true.
Для каждой ячейки, где i ≥ 1 и j ≥ 1, если p[j-1] — звёздочка, установи её значение в dp[i][j-2] или (p[j-2] соответствует s[i-1] и dp[i-1][j]).
В противном случае установи её значение в (p[j-1] соответствует s[i-1]) и dp[i-1][j-1].
Верни dp[n][m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

Оставьте только две строки

Идея

Строка i считывает две ячейки из строки i-1: диагональную и ячейку сверху, а также одну ячейку той же строки, на две позиции левее. К более ранним строкам больше не обращаются. Используйте два массива: prev для завершённой строки и cur для строки, которую вы заполняете, и меняйте их местами после каждой буквы s. Переходы остаются прежними: ноль копий — это cur[j-2], ещё одна копия — prev[j], обычное совпадение — prev[j-1].

Начните с prev в качестве базовой строки для пустой строки. В начале каждой строки задавайте cur[0] значение false: после обмена cur содержит старую строку, а первая ячейка базовой строки имеет значение true.

В каждой строке m + 1 ячеек, поэтому объём памяти сокращается примерно с 10^6 ячеек до двух строк по 1001 ячейке. В отличие от расстояния редактирования, нельзя поменять два входных значения местами, чтобы сделать строки короче, потому что строка и шаблон играют разные роли.

Алгоритм

Заполни prev базовой строкой: true в позиции 0, а в позиции j, если p[j-1] — звёздочка и prev[j-2] равно true.
Для каждой буквы в s установи cur[0] в false.
Заполни cur[1..m]: в ячейке со звёздочкой значение равно cur[j-2] или (элемент совпадает и prev[j]); в любой другой ячейке — (элемент совпадает) и prev[j-1].
Поменяй местами prev и cur.
Верни prev[m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

Ловушки и крайние случаи

Большинство неправильных ответов возникает из-за звёздочки: что она повторяет, сколько раз и где она может сопоставиться с пустой строкой.

Позволять звёздочке захватывать столько букв, сколько возможно. a*a для aaa — это совпадение, но жадная a* поглощает все три буквы, и последняя a не подходит.
Использовать dp[i-1][j-2] для ещё одного повторения. Так звёздочка может захватить не больше одной буквы, поэтому aa для a* даёт false. Оставайся в столбце звёздочки: dp[i-1][j].
Оставлять всю строку 0 равной false, кроме первой ячейки. Тогда b для a*b не подходит, потому что перед b выражение a* должно сопоставиться с пустым префиксом.
Сравнивать s[i-1] со звёздочкой, а не с её элементом p[j-2].
Считать, что * означает «любой текст», как в шаблонах имён файлов. Здесь она повторяет только стоящий перед ней элемент; «любой текст» — это .*.
Принимать частичное совпадение. t.e подходит к началу tree, но ответ — false, потому что остаётся лишняя буква.
Забывать cur[0] = false в версии с двумя строками. После первого обмена cur[0] содержит true из базовой строки.

Частые вопросы4

Какова временная сложность сопоставления с регулярным выражением?

Решение с таблицей работает за время O(n × m), где n — длина s, а m — длина p, поскольку каждая ячейка считывает не более двух других. Для полной таблицы требуется O(n × m) памяти, а для двух строк — O(m). Простая рекурсия может работать экспоненциальное время на шаблонах с большим количеством звёздочек.

Почему ячейка со звёздочкой считывает ячейку сверху, а не по диагонали?

Ячейка выше, dp[i-1][j], содержит тот же шаблон, но строка s на одну букву короче, а звёздочка всё ещё в нём. Поэтому после того, как звёздочка поглотит s[i-1], она может поглотить и s[i-2], и так далее вверх по столбцу. Ячейка по диагонали dp[i-1][j-2] удаляет звёздочку после одной буквы, что позволяет использовать ровно одну копию, а не любое количество.

Чем это отличается от сопоставления с подстановочными знаками?

При сопоставлении с шаблонами с подстановочными знаками, как и в шаблонах имён файлов, * используется самостоятельно и соответствует любой последовательности символов, а ? соответствует одному символу. Здесь * повторяет только предшествующий ему элемент, а шаблон для любого текста — .*. Оба варианта решаются с помощью таблицы по префиксам, но переход для звёздочки различается: при сопоставлении с подстановочными знаками читается dp[i][j-1] или dp[i-1][j].

Почему бы не использовать библиотеку регулярных выражений языка?

Интервьюеру нужен алгоритм, а не вызов библиотеки. Существует и реальный риск: многие движки регулярных выражений выполняют сопоставление с помощью возврата с отслеживанием, то есть медленной рекурсии из первого подхода. Шаблон вроде десяти копий a*, за которыми следует b, при проверке длинной последовательности букв a может заставить такой движок работать несколько минут. Таблица всегда завершает работу за O(n × m).

Python

def isMatch(s, p):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "moon"
p = "mo*n"

Ожидается

true

Regular Expression Matching

Функция

Ограничения

Примеры

Подсказки

Решение

Сопоставление слева с помощью рекурсии

Заполните таблицу префиксов

Оставьте только две строки

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи