Regular Expression Matching

Q: Jaka jest złożoność czasowa dopasowywania wyrażeń regularnych?

Rozwiązanie z tabelą działa w czasie O(n × m) dla ciągu znaków o długości n i wzorca o długości m , ponieważ każda komórka odczytuje najwyżej dwie inne. Pełna tabela wymaga O(n × m) pamięci, a dwie jej wiersze — O(m) . Zwykła rekurencja może działać w czasie wykładniczym dla wzorców zawierających wiele gwiazdek.

TrudneProgramowanie dynamiczne Rekurencja

+10

Otrzymujesz ciąg znaków s i wzorzec p. Wzorzec dopasowuje daną literę do tej samej litery, kropka . dopasowuje dowolną pojedynczą literę, a gwiazdka * oznacza zero lub więcej wystąpień elementu bezpośrednio przed nią, którym jest litera lub kropka. Zwróć true, jeśli wzorzec dopasowuje cały ciąg s, a w przeciwnym razie false.

Funkcja

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

sstring: ciąg znaków do dopasowania, tylko małe litery
pstring: wzór z liter, kropek i gwiazdek
Zwracaboolean: true, jeśli p pasuje do całego s, w przeciwnym razie false

Ograniczenia

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s zawiera wyłącznie małe litery alfabetu angielskiego.
p zawiera wyłącznie małe litery angielskiego alfabetu, . i *.
Każdy znak * występuje po literze lub ., więc p nigdy nie zaczyna się od * i nigdy nie ma dwóch gwiazdek z rzędu.

Przykłady

Wejście: s = "moon"p = "mo*n"
Wyjście: true
Wyjaśnienie: o* uwzględnia obie litery o, więc m, o* i n tworzą dokładnie moon.

Wejście: s = "tree"p = "t.e"
Wyjście: false
Wyjaśnienie: t.e pasuje do tre, początku tree, ale ostatnie e pozostaje, a dopasowanie musi obejmować całe s.

Wejście: s = "sky"p = "z*s.*y"
Wyjście: true
Wyjaśnienie: z* oznacza zero wystąpień z, s dopasowuje s, .* oznacza k, a y dopasowuje y.

Pytanie dodatkowe

Czy możesz również obsługiwać +, jedną lub więcej kopii elementu przed nim, za pomocą tej samej tabeli?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Gwiazdka może oznaczać dowolną liczbę powtórzeń, a właściwa liczba zależy od tego, co po niej następuje. Potraktuj literę i jej gwiazdkę jako jedną całość z dwoma możliwościami: pominąć ją albo dopasować jedną literę i pozostać przy niej. Tabela pokazująca, które prefiksy s pasują do których prefiksów p, sprawdza każdą możliwość dokładnie raz.

Dopasuj od lewej za pomocą rekurencji

Poprawne, ale nie kończy się na największych testach

Intuicja

Porównaj sufiksy: match(i, j) określa, czy s[i:] pasuje do p[j:]. Litera lub kropka bez gwiazdki musi pasować do s[i], a reszta również musi pasować. Element x* albo przyjmuje zero kopii i jest pomijany, albo pochłania s[i] i pozostaje przy tym samym elemencie — tak jedna gwiazdka może dopasować dowolną liczbę liter. Te dwie gałęzie obejmują wszystkie możliwości, jakie daje gwiazdka, więc żadne dopasowanie nie zostanie pominięte.

Każda gwiazdka dzieli wyszukiwanie na dwie części. Dla 30 liter a i dziesięciu wystąpień a*, po których następuje b, rekurencja wypróbowuje około 8.5 × 10^8 sposobów rozdzielenia liter między gwiazdki, zanim zwróci false, mimo że istnieje tylko (n+1) × (m+1) różnych par (i, j).

Algorytm

Zapisz match(i, j) dla sufiksów zaczynających się od i i j.
Jeśli j wykracza poza koniec p, zwróć informację, czy i wykracza poza koniec s.
Ustaw first na wartość określającą, czy s[i] istnieje oraz czy p[j] jest równe s[i] lub kropce.
Jeśli p[j+1] jest gwiazdką, zwróć match(i, j+2) lub first and match(i+1, j).
W przeciwnym razie zwróć first and match(i+1, j+1). Odpowiedzią jest 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)

Uzupełnij tabelę przedrostków

Intuicja

Niech dp[i][j] określa, czy pierwsze i liter ciągu s pasują do pierwszych j znaków wzorca p. dp[0][0] ma wartość true. W wierszu 0 pusty ciąg pasuje do prefiksu wzorca tylko wtedy, gdy każdy jego element jest oznaczony gwiazdką, np. z* lub a*b*.

Litera lub kropka w p[j-1] musi pasować do s[i-1], a pozostała część również musi pasować: komórka po przekątnej, dp[i-1][j-1]. Gwiazdka z elementem x = p[j-2] daje dwie możliwości. Zero wystąpień pomija x*: dp[i][j-2]. Jedno dodatkowe wystąpienie, gdy x pasuje do s[i-1], pozostawia to samo x*, aby dopasować krótszy ciąg: dp[i-1][j], komórkę powyżej. Każde wystąpienie to jeden krok w górę kolumny gwiazdki. Dla sky i z*s.*y kolumna z*s.* ma wartość true dla s dzięki zeru wystąpień, a następnie dla sk i sky po jednym kroku w górę.

Każda komórka odczytuje wiersz powyżej lub komórki po swojej lewej stronie, więc wypełnianie wiersz po wierszu zapewnia, że są już gotowe.

Algorytm

Utwórz tablicę dp z (n+1) × (m+1) wartościami false i ustaw dp[0][0] na true.
Dla j od 2 do m ustaw dp[0][j] na true, gdy p[j-1] jest gwiazdką, a dp[0][j-2] ma wartość true.
Dla każdej komórki, w której i ≥ 1 i j ≥ 1, jeśli p[j-1] jest gwiazdką, ustaw jej wartość na dp[i][j-2] lub (p[j-2] pasuje do s[i-1] i dp[i-1][j]).
W przeciwnym razie ustaw jej wartość na (p[j-1] pasuje do s[i-1]) i dp[i-1][j-1].
Zwróć 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]

Zachowaj tylko dwa wiersze

Intuicja

Wiersz i odczytuje tylko dwie komórki wiersza i-1: po przekątnej i komórkę powyżej, a także własną komórkę oddaloną o dwie pozycje w lewo. Zachowaj dwie tablice, prev i cur, i zamieniaj je miejscami po każdej literze ciągu s: zero kopii to cur[j-2], jedna dodatkowa kopia to prev[j], a zwykłe dopasowanie to prev[j-1]. Zużycie pamięci spada z około 10^6 komórek do dwóch wierszy po 1001 komórek. Nie możesz zamienić wejść miejscami, żeby skrócić wiersze, ponieważ ciąg i wzorzec pełnią różne role.

Algorytm

Wypełnij prev wierszem 0 tabeli.
Dla każdej litery w s ustaw cur[0] na false i wypełnij cur[1..m] zgodnie z regułami tabeli, odczytując prev z wiersza powyżej.
Zamień miejscami prev i cur.
Zwróć 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]

Pułapki i przypadki brzegowe

Pozwolenie gwiazdce na dopasowanie tylu liter, ilu tylko może. a*a pasuje do aaa, ale zachłanne a* pochłania wszystkie trzy litery, przez co ostatnie a nie pasuje.
Odczytywanie dp[i-1][j-2] dla jeszcze jednej kopii. Dzięki temu gwiazdka może dopasować najwyżej jedną literę, więc aa w porównaniu z a* daje wynik false.
Pozostawienie wiersza 0 jako false po pierwszej komórce. Wtedy b w porównaniu z a*b nie pasuje, ponieważ b wymaga, aby a* pasowało do pustego prefiksu.
Porównywanie s[i-1] z gwiazdką zamiast z jej elementem p[j-2]. Wtedy a w porównaniu z a* nie pasuje.
Nieustawianie cur[0] z powrotem na false w wersji z dwoma wierszami. Po zamianie może zawierać true z wiersza bazowego, przez co aab w porównaniu z b daje wynik true.

Najczęstsze pytania3

Jaka jest złożoność czasowa dopasowywania wyrażeń regularnych?

Rozwiązanie z tabelą działa w czasie O(n × m) dla ciągu znaków o długości n i wzorca o długości m, ponieważ każda komórka odczytuje najwyżej dwie inne. Pełna tabela wymaga O(n × m) pamięci, a dwie jej wiersze — O(m). Zwykła rekurencja może działać w czasie wykładniczym dla wzorców zawierających wiele gwiazdek.

Jak to się różni od dopasowywania za pomocą symboli wieloznacznych?

W dopasowywaniu wieloznaczników, podobnie jak we wzorcach nazw plików, * występuje samodzielnie i dopasowuje dowolny ciąg znaków, a ? dopasowuje jeden znak. Tutaj * powtarza tylko poprzedzający go element, a dowolny tekst to .*. Oba rozwiązania wykorzystują tabelę prefiksów, ale gwiazdka wieloznacznika odczytuje dp[i][j-1] lub dp[i-1][j].

Dlaczego nie użyć biblioteki wyrażeń regularnych danego języka?

Osoba prowadząca rozmowę kwalifikacyjną chce poznać algorytm, a nie wywołanie biblioteki. Wiele silników wyrażeń regularnych również dopasowuje wzorce za pomocą nawrotów, czyli wolnej rekurencji z pierwszego podejścia, więc dziesięć kopii a*, po których następuje b, dopasowywanych do długiego ciągu liter a, może sprawić, że będą działać przez kilka minut. Algorytm z tabelą zawsze kończy działanie w czasie O(n × m).

def isMatch(s, p):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

true

Regular Expression Matching

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Dopasuj od lewej za pomocą rekurencji

Uzupełnij tabelę przedrostków

Zachowaj tylko dwa wiersze

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania