Regular Expression Matching

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

Rozwiązanie z użyciem tabeli działa w czasie O(n × m) , gdzie n to długość s , a m to długość p , ponieważ każda komórka odczytuje co najwyżej dwie inne. Pełna tabela wymaga O(n × m) pamięci, a dwa wiersze O(m) . Zwykła rekurencja może działać w czasie wykładniczym dla wzorców z wieloma gwiazdkami.

Q: Dlaczego komórka z gwiazdką odczytuje komórkę powyżej, a nie po przekątnej?

Komórka powyżej, dp[i-1][j] , przedstawia ten sam wzorzec, ale z jedną literą mniej w s , a gwiazdka nadal w nim pozostaje. Po zjedzeniu przez gwiazdkę s[i-1] może więc ona zjeść również s[i-2] i tak dalej w górę kolumny. Komórka po przekątnej, dp[i-1][j-2] , usuwa gwiazdkę po jednej literze, co pozwala na dokładnie jedno wystąpienie zamiast dowolnej liczby.

TrudneProgramowanie dynamiczne Rekurencja

+10

Otrzymujesz ciąg znaków s i wzorzec p. We wzorcu litera dopasowuje tę samą literę, 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 pasuje do całego ciągu s, a nie tylko do jego części, 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 alfabetu angielskiego, . i *.
Każde * 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* obejmuje 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 tylko do ciągów składających się z trzech liter: t, dowolna litera, a następnie e. Pasuje do tre na 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. Litera z gwiazdką może oznaczać nic, więc z, które nigdy nie pojawia się w sky, nic nie kosztuje.

+29 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz też obsłużyć +, czyli jedną lub więcej kopii poprzedzającego go elementu, przy użyciu 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ę kopii, a właściwa liczba zależy od tego, co występuje po niej. Dopasowanie jak największej liczby nie działa: dla aaa wzorzec a*a pozwala a* pochłonąć wszystkie trzy litery, przez co dla ostatniego a nic nie zostaje. Pomysł, który rozwiązuje ten problem, polega na potraktowaniu litery i jej gwiazdki jako jednej jednostki z dwoma możliwościami: pominąć ją albo pozwolić jej pochłonąć jedną literę i pozostać na swoim miejscu. Tablica przechowuje informację, czy każdy prefiks s pasuje do każdego prefiksu p, dzięki czemu każda możliwość jest sprawdzana raz, a wystarczą dwa jej wiersze.

Dopasuj od lewej z użyciem rekurencji

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

Intuicja

Niech match(i, j) określa, czy sufiks s[i:] pasuje do sufiksu p[j:]. Jeśli wzorzec się skończył, pasuje tylko wtedy, gdy skończył się również ciąg. W przeciwnym razie oblicz first: istnieje litera s[i], a p[j] jest tą literą lub kropką.

Teraz spójrz o jeden znak dalej. Jeśli p[j+1] jest gwiazdką, p[j]* stanowi jedną jednostkę z dwoma możliwymi ruchami. Można wziąć zero kopii: pominąć oba znaki, używając match(i, j+2). Albo, jeśli zachodzi first, można wziąć jedną kopię: zużyć s[i] i pozostać przy tej samej jednostce, używając match(i+1, j), gotowym na wzięcie kolejnej. Pozostanie przy j pozwala jednej gwiazdce dopasować dowolną liczbę liter, po jednej naraz. Bez gwiazdki p[j] musi dokładnie pasować do jednej litery: first and match(i+1, j+1).

To działa wolno, ponieważ każda gwiazdka rozdziela wyszukiwanie na dwie gałęzie, a niepowodzenie często zostaje wykryte dopiero na samym końcu. Weź 30 liter a, dziesięć kopii a*, a po nich literę b. Rekurencja wypróbowuje każdy sposób rozdzielenia części lub całości 30 liter a między dziesięć gwiazdek — około 8.5 × 10^8 możliwości — i wykonuje około 2 × 10^9 wywołań, zanim może zwrócić false. Duże testy mają 1000 liter. A jednak istnieje tylko (n+1) × (m+1) różnych par (i, j).

Algorytm

Zapisz match(i, j) dla sufiksów zaczynających się na pozycjach i i j.
Jeśli j znajduje się za końcem p, zwróć informację, czy i znajduje się za końcem s.
Ustaw first na wartość określającą, czy s[i] istnieje, a p[j] jest równe s[i] lub jest kropką.
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ę prefiksów

Intuicja

Stan. Niech dp[i][j] określa, czy pierwsze i liter ciągu s pasują do pierwszych j znaków wzorca p. Indeks 0 oznacza pusty prefiks.

Wiersz i kolumna bazowa. dp[0][0] ma wartość true: pusty wzorzec pasuje do pustego ciągu. Pozostałe komórki kolumny 0 mają wartość false, ponieważ pusty wzorzec nie może pasować do litery. Wiersz 0 jest mniej oczywisty: prefiks wzorca pasuje do pustego ciągu tylko wtedy, gdy każdy jego element ma gwiazdkę, na przykład z* lub a*b*. Zatem dp[0][j] ma wartość true, gdy p[j-1] jest gwiazdką, a dp[0][j-2] ma wartość true.

Przejścia. Jeśli p[j-1] jest literą lub kropką, musi pasować do ostatniej litery s[i-1], a pozostała część również musi pasować: dp[i-1][j-1], czyli komórka po przekątnej. Jeśli p[j-1] jest gwiazdką, jej elementem jest x = p[j-2], a gwiazdka ma dwa możliwe ruchy. Zero powtórzeń: usuń x* ze wzorca, dp[i][j-2], czyli przejdź o dwie komórki w lewo. Jeszcze jedno powtórzenie: jeśli x pasuje do s[i-1], ta litera jest jednym z powtórzeń, a to samo x* nadal musi dopasować krótszy ciąg, więc odczytaj dp[i-1][j], komórkę bezpośrednio powyżej, w tej samej kolumnie. Każde powtórzenie to jeden krok w górę tej kolumny, dzięki czemu pojedyncza gwiazdka może obejmować dowolną liczbę liter.

Oto tabela dla sky i z*s.*y, z kolumnami dla prefiksów "", z, z*, z*s, z*s., z*s.*, z*s.*y (T oznacza true, F oznacza false). Wiersz "" to [T, F, T, F, F, F, F]: pusty może być tylko wzorzec z*. Wiersz s to [F, F, F, T, F, T, F]: s pasuje do s, a z* nad nim jest puste — wskazuje na to komórka po przekątnej; następnie .* przyjmuje zero powtórzeń. Wiersz sk to [F, F, F, F, T, T, F]: komórka dla z*s.* otrzymuje wartość true dzięki jeszcze jednemu powtórzeniu — k zostaje dopasowane przez kropkę, co wynika z wartości T w komórce bezpośrednio powyżej. Wiersz sky to [F, F, F, F, F, T, T]: kropka z gwiazdką dopasowuje y w ten sam sposób, jako drugi krok w górę kolumny, a następnie y pasuje do y po przekątnej. Wartość ostatniej komórki to true.

Każda komórka odczytuje wartości z wiersza powyżej lub komórek po swojej lewej stronie, więc wypełnianie tabeli wiersz po wierszu, od lewej do prawej, zapewnia, że potrzebne wartości są już obliczone. To (n+1) × (m+1) komórek, około 10^6 dla największych testów, a obliczenie każdej z nich wymaga stałej liczby operacji.

Algorytm

Utwórz tablicę dp złożoną z (n+1) × (m+1) wartości 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, dla której i ≥ 1 i j ≥ 1, jeśli p[j-1] jest gwiazdką, ustaw ją na dp[i][j-2] lub (p[j-2] pasuje do s[i-1] i dp[i-1][j]).
W przeciwnym razie ustaw ją 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 dwie komórki z wiersza i-1: komórkę po przekątnej i komórkę powyżej, a także jedną komórkę z tego samego wiersza, oddaloną o dwie pozycje w lewo. Wiersze położone wyżej nie są już odczytywane. Zachowaj dwie tablice: prev dla ukończonego wiersza i cur dla wiersza, który wypełniasz, a po każdej literze s zamieniaj je miejscami. Przejścia pozostają takie same: zero kopii to cur[j-2], jedna dodatkowa kopia to prev[j], a zwykłe dopasowanie to prev[j-1].

Zacznij od prev jako wiersza bazowego dla pustego ciągu. Na początku każdego wiersza ustaw cur[0] na false: po zamianie miejscami cur zawiera stary wiersz, a pierwsza wartość wiersza bazowego to true.

Każdy wiersz ma m + 1 wpisów, więc zużycie pamięci spada z około 10^6 komórek do dwóch wierszy po 1001 komórek. W przeciwieństwie do odległości edycyjnej nie możesz zamienić miejscami dwóch wejściowych ciągów, aby skrócić wiersze, ponieważ ciąg znaków i wzorzec pełnią różne role.

Algorytm

Wypełnij prev wierszem bazowym: wartość true dla 0 oraz dla j, gdy p[j-1] jest gwiazdką, a prev[j-2] ma wartość true.
Dla każdej litery w s ustaw cur[0] na false.
Wypełnij cur[1..m]: w komórce z gwiazdką wpisz cur[j-2] lub (element pasuje i prev[j]); w każdej innej komórce wpisz (element pasuje) i prev[j-1].
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

Większość błędnych odpowiedzi wynika z gwiazdki: co powtarza, ile razy i gdzie może dopasować pusty ciąg.

Pozwalanie gwiazdce dopasować tyle liter, ile 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] przy kolejnej kopii. To pozwala gwiazdce dopasować najwyżej jedną literę, więc aa w porównaniu z a* daje wynik false. Pozostań w kolumnie gwiazdki: dp[i-1][j].
Pozostawianie wiersza 0 wypełnionego wartościami false, z wyjątkiem pierwszej komórki. Wtedy b w porównaniu z a*b nie pasuje, ponieważ b wymaga, by a* dopasowało pusty prefiks przed nim.
Porównywanie s[i-1] z samą gwiazdką zamiast z jej elementem p[j-2].
Traktowanie * jako „dowolnego tekstu”, jak we wzorcach nazw plików. Tutaj powtarza tylko poprzedzający go element; dowolny tekst to .*.
Akceptowanie częściowego dopasowania. t.e pasuje do początku tree, ale odpowiedź to false, ponieważ pozostaje jedna litera.
Zapominanie o cur[0] = false w wersji z dwoma wierszami. Po pierwszej zamianie cur[0] zawiera wartość true z wiersza bazowego.

Najczęstsze pytania4

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

Rozwiązanie z użyciem tabeli działa w czasie O(n × m), gdzie n to długość s, a m to długość p, ponieważ każda komórka odczytuje co najwyżej dwie inne. Pełna tabela wymaga O(n × m) pamięci, a dwa wiersze O(m). Zwykła rekurencja może działać w czasie wykładniczym dla wzorców z wieloma gwiazdkami.

Dlaczego komórka z gwiazdką odczytuje komórkę powyżej, a nie po przekątnej?

Komórka powyżej, dp[i-1][j], przedstawia ten sam wzorzec, ale z jedną literą mniej w s, a gwiazdka nadal w nim pozostaje. Po zjedzeniu przez gwiazdkę s[i-1] może więc ona zjeść również s[i-2] i tak dalej w górę kolumny. Komórka po przekątnej, dp[i-1][j-2], usuwa gwiazdkę po jednej literze, co pozwala na dokładnie jedno wystąpienie zamiast dowolnej liczby.

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

W dopasowywaniu symboli wieloznacznych, 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 wzorzec dopasowujący dowolny tekst to .*. Oba problemy rozwiązuje się za pomocą tabeli prefiksów, ale przejście dla gwiazdki jest inne: w dopasowywaniu symboli wieloznacznych odczytuje się dp[i][j-1] lub dp[i-1][j].

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

Osoba przeprowadzająca rozmowę kwalifikacyjną chce poznać algorytm, a nie wywołanie biblioteczne. Istnieje też realne ryzyko: wiele silników wyrażeń regularnych dopasowuje wzorce metodą nawrotów, czyli przez powolną rekurencję z pierwszego podejścia. Wzorzec taki jak dziesięć kopii a*, po których następuje b, dopasowywany do długiego ciągu liter a, może sprawić, że taki silnik będzie działał przez wiele minut. Tabela zawsze kończy działanie w czasie O(n × m).

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

true

Regular Expression Matching

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Dopasuj od lewej z użyciem rekurencji

Uzupełnij tabelę prefiksów

Zachowaj tylko dwa wiersze

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania