Regular Expression Matching

Q: Wie unterscheidet sich das vom Platzhaltermusterabgleich?

Beim Abgleich mit Platzhaltern steht * wie bei Dateinamensmustern für sich allein und entspricht einer beliebigen Zeichenfolge, und ? entspricht einem einzelnen Zeichen. Hier wiederholt * nur das Element davor, und beliebiger Text ist .* . Beide verwenden eine Tabelle über Präfixe, aber der Platzhalter-Stern liest dp[i][j-1] oder dp[i-1][j] .

SchwerDynamische Programmierung Rekursion

+10

Du erhältst eine Zeichenfolge s und ein Muster p. Im Muster entspricht ein Buchstabe genau demselben Buchstaben, ein Punkt . entspricht einem beliebigen einzelnen Buchstaben und ein Sternchen * bedeutet null oder mehr Wiederholungen des Elements direkt davor, also eines Buchstabens oder eines Punkts. Gib true zurück, wenn das Muster auf die gesamte Zeichenfolge s passt, andernfalls false.

Funktion

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

sstring: die abzugleichende Zeichenfolge, nur Kleinbuchstaben
pstring: das Muster aus Buchstaben, Punkten und Sternen
Gibt zurückboolean: wahr, wenn p auf alle Elemente von s zutrifft, andernfalls falsch

Einschränkungen

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s enthält nur englische Kleinbuchstaben.
p enthält nur englische Kleinbuchstaben, . und *.
Jedes * folgt auf einen Buchstaben oder ein ., daher beginnt p nie mit * und enthält nie zwei Sterne hintereinander.

Beispiele

Eingabe: s = "moon"p = "mo*n"
Ausgabe: true
Erklärung: o* nimmt beide o-Buchstaben, also ergeben m, o* und n genau moon.

Eingabe: s = "tree"p = "t.e"
Ausgabe: false
Erklärung: t.e passt zu tre, dem Anfang von tree, aber das letzte e bleibt übrig, und eine Übereinstimmung muss das gesamte s abdecken.

Eingabe: s = "sky"p = "z*s.*y"
Ausgabe: true
Erklärung: z* entspricht null Vorkommen von z, s entspricht s, .* nimmt das k auf, und y entspricht y.

Weiterführende Frage

Kannst du mit derselben Tabelle auch + unterstützen, also eine oder mehrere Wiederholungen des Elements davor?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Stern kann für beliebig viele Wiederholungen stehen, und die richtige Anzahl hängt davon ab, was danach kommt. Behandle einen Buchstaben und seinen Stern als eine Einheit mit zwei Möglichkeiten: ihn überspringen oder einen Buchstaben verbrauchen und dabei auf ihm bleiben. Eine Tabelle, die festhält, welche Präfixe von s zu welchen Präfixen von p passen, probiert jede Auswahl einmal aus.

Von links mit Rekursion abgleichen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Vergleiche die Suffixe: match(i, j) gibt an, ob s[i:] zu p[j:] passt. Ein Buchstabe oder Punkt ohne Stern muss zu s[i] passen, und der Rest muss ebenfalls passen. Eine Einheit x* nimmt entweder null Kopien und wird übersprungen oder verbraucht s[i] und bleibt bei derselben Einheit. So kann ein Stern beliebig viele Buchstaben aufnehmen. Die beiden Zweige decken alle Möglichkeiten ab, die ein Stern hat, sodass kein Treffer übersehen wird.

Jeder Stern teilt die Suche in zwei Zweige auf. Bei 30 Buchstaben a, zehn Kopien von a* und danach einem b probiert die Rekursion etwa 8.5 × 10^8 Möglichkeiten aus, die Buchstaben auf die Sterne zu verteilen, bevor sie mit false antwortet. Es gibt jedoch nur (n+1) × (m+1) verschiedene Paare (i, j).

Algorithmus

Schreibe match(i, j) für die Suffixe, die bei i und j beginnen.
Wenn j hinter dem Ende von p liegt, gib zurück, ob i hinter dem Ende von s liegt.
Setze first darauf, ob s[i] existiert und p[j] entweder s[i] oder ein Punkt ist.
Wenn p[j+1] ein Sternchen ist, gib match(i, j+2) oder first and match(i+1, j) zurück.
Gib andernfalls first and match(i+1, j+1) zurück. Die Antwort ist 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)

Fülle eine Tabelle mit Präfixen aus

Idee

Sei dp[i][j] ein Wert, der angibt, ob die ersten i Buchstaben von s zu den ersten j Zeichen von p passen. dp[0][0] ist true. In Zeile 0 passt die leere Zeichenkette nur dann zu einem Präfix des Musters, wenn jedes Element darin mit einem Stern versehen ist, wie bei z* oder a*b*.

Ein Buchstabe oder Punkt an Position p[j-1] muss zu s[i-1] passen, und der Rest muss ebenfalls passen: das diagonale Feld, dp[i-1][j-1]. Ein Stern mit dem Element x = p[j-2] bietet zwei Möglichkeiten. Null Wiederholungen lassen x* weg: dp[i][j-2]. Eine weitere Wiederholung lässt, wenn x zu s[i-1] passt, dasselbe x* übrig, um die kürzere Zeichenkette abzugleichen: dp[i-1][j], das Feld darüber. Jede Wiederholung ist ein Schritt nach oben in der Spalte des Sterns. Für sky und z*s.*y ist die Spalte von z*s.* für s durch null Wiederholungen true, dann jeweils einen Schritt weiter oben für sk und sky.

Jedes Feld liest aus der Zeile darüber oder aus Feldern links davon, daher sind die benötigten Werte beim Ausfüllen Zeile für Zeile bereits vorhanden.

Algorithmus

Erstelle eine Tabelle dp mit (n+1) × (m+1) falschen Werten und setze dp[0][0] auf wahr.
Setze für j von 2 bis m dp[0][j] auf wahr, wenn p[j-1] ein Sternchen ist und dp[0][j-2] wahr ist.
Setze für jede Zelle mit i ≥ 1 und j ≥ 1, wenn p[j-1] ein Sternchen ist, ihren Wert auf dp[i][j-2] oder (p[j-2] mit s[i-1] übereinstimmt und dp[i-1][j]).
Andernfalls setze ihren Wert auf (p[j-1] stimmt mit s[i-1] überein) und dp[i-1][j-1].
Gib dp[n][m] zurück.

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]

Behalte nur zwei Zeilen

Idee

Zeile i liest nur zwei Zellen aus Zeile i-1: die diagonale Zelle und die Zelle darüber, sowie ihre eigene Zelle zwei Positionen weiter links. Verwende zwei Arrays, prev und cur, und vertausche sie nach jedem Buchstaben von s: null Kopien entsprechen cur[j-2], eine weitere Kopie entspricht prev[j], und eine einfache Übereinstimmung entspricht prev[j-1]. Der Speicherbedarf sinkt von etwa 10^6 Zellen auf zwei Zeilen mit je 1001 Zellen. Du kannst die Eingaben nicht vertauschen, um die Zeilen zu verkürzen, denn der String und das Muster erfüllen unterschiedliche Aufgaben.

Algorithmus

Fülle prev mit Zeile 0 der Tabelle.
Setze für jeden Buchstaben von s cur[0] auf false und fülle cur[1..m] gemäß den Regeln der Tabelle, wobei du prev für die darüberliegende Zeile verwendest.
Tausche prev und cur.
Gib prev[m] zurück.

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]

Stolperfallen und Grenzfälle

Einen Stern so viele Buchstaben wie möglich zuordnen lassen. a*a passt auf aaa, aber ein gieriges a* verbraucht alle drei Buchstaben, und das letzte a passt dann nicht.
dp[i-1][j-2] für eine weitere Kopie lesen. Dadurch kann ein Stern höchstens einen Buchstaben zuordnen, also ergibt aa gegen a* false.
Zeile 0 nach ihrer ersten Zelle auf false belassen. Dann schlägt b gegen a*b fehl, weil das b a* benötigt, um auf das leere Präfix zu passen.
s[i-1] mit dem Stern statt mit seinem Element p[j-2] vergleichen. Dann schlägt a gegen a* fehl.
cur[0] in der Version mit zwei Zeilen nicht auf false zurücksetzen. Nach einem Tausch kann darin das true der Basiszeile stehen, und aab gegen b ergibt true.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Abgleichs regulärer Ausdrücke?

Die Tabellenlösung benötigt für eine Zeichenfolge der Länge n und ein Muster der Länge m eine Laufzeit von O(n × m), da jede Zelle höchstens zwei andere Zellen ausliest. Für die vollständige Tabelle benötigt sie O(n × m) Speicher oder mit zwei Zeilen O(m). Eine einfache Rekursion kann bei Mustern mit vielen Sternen exponentielle Laufzeit haben.

Wie unterscheidet sich das vom Platzhaltermusterabgleich?

Beim Abgleich mit Platzhaltern steht * wie bei Dateinamensmustern für sich allein und entspricht einer beliebigen Zeichenfolge, und ? entspricht einem einzelnen Zeichen. Hier wiederholt * nur das Element davor, und beliebiger Text ist .*. Beide verwenden eine Tabelle über Präfixe, aber der Platzhalter-Stern liest dp[i][j-1] oder dp[i-1][j].

Warum nicht die Regex-Bibliothek der Sprache verwenden?

Ein Interviewer möchte den Algorithmus sehen, nicht den Aufruf einer Bibliothek. Viele Regex-Engines arbeiten außerdem mit Backtracking, der langsamen Rekursion des ersten Ansatzes. Daher können zehn Kopien von a*, gefolgt von b, bei einem langen Lauf aus a-Buchstaben dazu führen, dass sie minutenlang laufen. Die Tabelle wird immer in O(n × m) fertig.

def isMatch(s, p):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

true

Regular Expression Matching

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Von links mit Rekursion abgleichen

Fülle eine Tabelle mit Präfixen aus

Behalte nur zwei Zeilen

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben