Regular Expression Matching

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

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

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

+10

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

Функция

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

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

Ограничения

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 подходит к tre, началу tree, но последняя e остаётся лишней, а совпадение должно охватывать всю строку s.

Ввод: s = "sky"p = "z*s.*y"
Вывод: true
Пояснение: z* соответствует нулю вхождений z, s соответствует s, .* соответствует k, а y соответствует y.

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

Можешь также поддержать + — одну или несколько копий элемента перед ним — с той же таблицей?

Подсказки

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

Открыто 0 из 3

Решение

Звёздочка может соответствовать любому количеству повторений, а нужное количество зависит от того, что идёт после неё. Рассматривай букву вместе со звёздочкой как единое целое с двумя действиями: пропустить её или поглотить одну букву и остаться на ней. Таблица, показывающая, какие префиксы s соответствуют каким префиксам p, перебирает каждый вариант ровно один раз.

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

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

Идея

Сравниваем суффиксы: match(i, j) сообщает, совпадает ли s[i:] с p[j:]. Буква или точка без звёздочки должна совпасть с s[i], а оставшаяся часть должна совпасть. Единица x* либо берёт ноль копий и пропускается, либо поглощает s[i] и остаётся на той же единице — так одна звёздочка может соответствовать любому количеству букв. Эти две ветви охватывают все варианты для звёздочки, поэтому ни одно совпадение не будет пропущено.

Каждая звёздочка делит поиск на две части. Для 30 букв a и десяти копий a*, за которыми следует b, рекурсия перебирает около 8.5 × 10^8 способов распределить буквы между звёздочками, прежде чем ответить false, хотя существует всего (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. dp[0][0] равно true. В строке 0 пустая строка совпадает с префиксом шаблона, только если каждый его элемент отмечен звёздочкой, например z* или a*b*.

Буква или точка в p[j-1] должна совпадать с s[i-1], а оставшаяся часть тоже должна совпадать: по диагонали, dp[i-1][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*s.* имеет значение true для s благодаря нулю вхождений, а затем для sk и sky — благодаря подъёму на один шаг каждый раз.

Каждая ячейка считывает значения из строки выше или из ячеек слева от неё, поэтому при заполнении по строкам нужные значения уже готовы.

Алгоритм

Создай таблицу 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]. Объём памяти сокращается примерно с 10^6 ячеек до двух строк по 1001 ячейке. Нельзя поменять входные данные местами, чтобы укоротить строки, потому что строка и шаблон играют разные роли.

Алгоритм

Заполните prev строкой 0 таблицы.
Для каждой буквы s установите cur[0] в false и заполните cur[1..m] по правилам таблицы, считывая prev из строки выше.
Поменяйте местами 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.
Оставлять строку 0 со значением false после первой ячейки. Тогда b не соответствует a*b, потому что для b нужно, чтобы a* соответствовало пустому префиксу.
Сравнивать s[i-1] со звёздочкой, а не с её элементом p[j-2]. Тогда a не соответствует a*.
Не сбрасывать cur[0] в false в версии с двумя строками. После обмена там может остаться true из базовой строки, и сравнение aab с b даст true.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргументы

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

Ожидаемый вывод

true

Regular Expression Matching

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

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

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

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

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