Regular Expression Matching

Q: Wie hoch ist die Zeitkomplexität des Abgleichs mit regulären Ausdrücken?

Die Tabellenlösung benötigt O(n × m) Zeit, wobei n die Länge von s und m die Länge von p ist, 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) . Einfache Rekursion kann bei Mustern mit vielen Sternchen exponentielle Laufzeit haben.

Q: Warum liest eine Sternzelle die Zelle darüber und nicht die diagonal gelegene Zelle?

Die Zelle darüber, dp[i-1][j] , folgt demselben Muster mit einem Buchstaben weniger von s , und der Stern ist noch enthalten. Nachdem der Stern also s[i-1] verschlungen hat, kann er auch s[i-2] verschlingen und so weiter nach oben in der Spalte. Die diagonal angeordnete Zelle dp[i-1][j-2] entfernt den Stern nach einem Buchstaben, wodurch genau eine Kopie statt beliebig vieler möglich ist.

Q: Wie unterscheidet sich das vom Abgleichen mit Platzhaltern?

Beim Abgleich mit Platzhaltern steht * wie bei Dateinamensmustern für sich allein und passt auf eine beliebige Folge von Zeichen, und ? passt auf ein Zeichen. Hier wiederholt * nur das Element davor, und das Muster für beliebigen Text ist .* . Beide werden mithilfe einer Tabelle über Präfixe gelöst, aber der Stern-Übergang unterscheidet sich: Beim Abgleich mit Platzhaltern werden dp[i][j-1] oder dp[i-1][j] gelesen.

SchwerDynamische Programmierung Rekursion

+10

Du erhältst eine Zeichenfolge s und ein Muster p. Im Muster stimmt ein Buchstabe mit demselben Buchstaben überein, ein Punkt . stimmt mit einem beliebigen einzelnen Buchstaben überein und ein Sternchen * bedeutet null oder mehr Wiederholungen des Elements direkt davor, also eines Buchstabens oder eines Punktes. Gib true zurück, wenn das Muster auf die gesamte Zeichenfolge s passt, nicht nur auf einen Teil davon, 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 ganz s passt, 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 *.
Auf jedes * folgt ein Buchstabe oder ein ., daher beginnt p nie mit * und enthält nie zwei Sternchen hintereinander.

Beispiele

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

Eingabe: s = "tree"p = "t.e"
Ausgabe: false
Erklärung: t.e passt nur auf Zeichenfolgen mit drei Buchstaben: t, ein beliebiger Buchstabe, dann e. Es passt am Anfang von tree auf tre, aber das letzte e bleibt übrig, und ein Treffer muss ganz s abdecken.

Eingabe: s = "sky"p = "z*s.*y"
Ausgabe: true
Erklärung: z* steht für null Vorkommen von z, s entspricht s, .* nimmt das k, und y entspricht y. Ein mit Stern versehenes Zeichen kann für nichts stehen, daher kostet ein z, das in sky nie vorkommt, nichts.

+29 versteckte Tests beim Einreichen

Weiterführende Frage

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

Tipps

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

0 von 3 geöffnet

Lösung

Ein Stern kann eine beliebige Anzahl von Zeichen aufnehmen, und die passende Anzahl hängt davon ab, was danach kommt. So viele wie möglich aufzunehmen, schlägt fehl: Bei aaa lässt das Muster a*a a* alle drei Buchstaben verschlingen, sodass für das letzte a nichts übrig bleibt. Der entscheidende Gedanke ist, einen Buchstaben und seinen Stern als eine Einheit mit zwei Möglichkeiten zu behandeln: ihn zu überspringen oder ihn einen Buchstaben aufnehmen zu lassen und an derselben Stelle zu bleiben. Eine Tabelle hält fest, ob jedes Präfix von s zu jedem Präfix von p passt, sodass jede Möglichkeit genau einmal ausprobiert wird; zwei Zeilen davon reichen aus.

Von links mit Rekursion abgleichen

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

Idee

Lass match(i, j) beantworten, ob das Suffix s[i:] zum Suffix p[j:] passt. Wenn das Muster aufgebraucht ist, passt es nur, wenn auch die Zeichenkette aufgebraucht ist. Berechne andernfalls first: Es gibt einen Buchstaben s[i], und p[j] ist dieser Buchstabe oder ein Punkt.

Betrachte nun das nächste Zeichen. Wenn p[j+1] ein Stern ist, ist p[j]* eine Einheit mit zwei möglichen Schritten. Sie kann null Vorkommen aufnehmen: Überspringe beide Zeichen mit match(i, j+2). Oder, wenn first zutrifft, kann sie ein Vorkommen aufnehmen: Verbrauche s[i] und bleibe mit match(i+1, j) auf derselben Einheit, bereit, ein weiteres aufzunehmen. Auf j zu bleiben ermöglicht es einem Stern, beliebig viele Buchstaben einzeln aufzunehmen. Ohne Stern muss p[j] genau einem Buchstaben entsprechen: first and match(i+1, j+1).

Das ist langsam, weil jeder Stern die Suche in zwei Teile aufteilt und ein Fehlschlag oft erst ganz am Ende gefunden wird. Nimm 30 a-Buchstaben, zehn Vorkommen von a* und danach ein b. Die Rekursion probiert jede Möglichkeit aus, einige oder alle der 30 a-Buchstaben auf die zehn Sterne zu verteilen – etwa 8.5 × 10^8 Möglichkeiten – und führt etwa 2 × 10^9 Aufrufe aus, bevor sie false zurückgeben kann. Die großen Tests haben 1000 Buchstaben. Dabei gibt es 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.
Andernfalls gib 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

Zustand. Lass dp[i][j] angeben, ob die ersten i Buchstaben von s zu den ersten j Zeichen von p passen. Index 0 steht für ein leeres Präfix.

Basiszeile und -spalte. dp[0][0] ist wahr: Ein leeres Muster passt zu einer leeren Zeichenfolge. Spalte 0 ist darunter falsch, weil ein leeres Muster nicht zu einem Buchstaben passen kann. Zeile 0 ist die knifflige: Ein Musterpräfix passt nur dann zur leeren Zeichenfolge, wenn jedes Element darin mit einem Stern versehen ist, wie bei z* oder a*b*. Also ist dp[0][j] wahr, wenn p[j-1] ein Stern ist und dp[0][j-2] wahr ist.

Übergänge. Wenn p[j-1] ein Buchstabe oder ein Punkt ist, muss es zum letzten Buchstaben s[i-1] passen, und der Rest muss ebenfalls passen: dp[i-1][j-1], die Diagonale. Wenn p[j-1] ein Stern ist, ist sein Element x = p[j-2], und der Stern hat zwei Möglichkeiten. Null Wiederholungen: Entferne x* aus dem Muster, dp[i][j-2], zwei Zellen nach links. Eine weitere Wiederholung: Wenn x zu s[i-1] passt, ist dieser Buchstabe eine der Wiederholungen, und dasselbe x* muss weiterhin die kürzere Zeichenfolge abgleichen. Lies also dp[i-1][j], die Zelle direkt darüber, in derselben Spalte. Jede Wiederholung ist ein Schritt nach oben in dieser Spalte. So kann ein einzelner Stern eine beliebige Anzahl von Buchstaben abdecken.

Hier ist die Tabelle für sky und z*s.*y, mit Spalten für die Präfixe "", z, z*, z*s, z*s., z*s.*, z*s.*y (T bedeutet wahr, F bedeutet falsch). Zeile "" ist [T, F, T, F, F, F, F]: Nur z* kann leer sein. Zeile s ist [F, F, F, T, F, T, F]: s passt zu s, wobei z* darüber auf der Diagonale leer ist, und .* nimmt anschließend null Wiederholungen. Zeile sk ist [F, F, F, F, T, T, F]: Die Zelle für z*s.* erhält ihren wahren Wert durch eine weitere Wiederholung; der Punkt nimmt k auf. Lies den T-Wert direkt darüber. Zeile sky ist [F, F, F, F, F, T, T]: Der Stern nach dem Punkt nimmt y auf dieselbe Weise auf, mit einem zweiten Schritt nach oben in der Spalte, und dann passt y auf der Diagonale zu y. Die letzte Zelle ist wahr.

Jede Zelle liest die Zeile darüber oder Zellen links von ihr, daher sind die benötigten Werte bereits vorhanden, wenn die Tabelle zeilenweise von links nach rechts ausgefüllt wird. Das sind (n+1) × (m+1) Zellen, etwa 10^6 bei den größten Tests, mit konstantem Aufwand pro Zelle.

Algorithmus

Erstelle eine Tabelle dp mit (n+1) × (m+1) falschen Werten und setze dp[0][0] auf true.
Setze für j von 2 bis m dp[0][j] auf true, wenn p[j-1] ein Stern ist und dp[0][j-2] true ist.
Setze für jede Zelle mit i ≥ 1 und j ≥ 1, falls p[j-1] ein Stern 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 zwei Zellen aus Zeile i-1 – die diagonale und die Zelle darüber – sowie eine eigene Zelle, zwei Positionen weiter links. Weiter oben liegende Zeilen werden nie wieder gelesen. Verwende zwei Arrays: prev für die fertige Zeile und cur für die Zeile, die du gerade ausfüllst, und tausche sie nach jedem Zeichen von s aus. Die Übergänge bleiben gleich: null Kopien entspricht cur[j-2], eine weitere Kopie entspricht prev[j], ein einfacher Treffer entspricht prev[j-1].

Beginne mit prev als Basiszeile für die leere Zeichenfolge. Setze cur[0] zu Beginn jeder Zeile auf false: Nach einem Tausch enthält cur eine alte Zeile, und der erste Eintrag der Basiszeile ist true.

Jede Zeile hat m + 1 Einträge, sodass der Speicherbedarf von etwa 10^6 Zellen auf zwei Zeilen mit je 1001 Einträgen sinkt. Anders als bei der Editierdistanz kannst du die beiden Eingaben nicht vertauschen, um die Zeilen kürzer zu machen, denn die Zeichenfolge und das Muster erfüllen unterschiedliche Rollen.

Algorithmus

Fülle prev mit der Basiszeile: wahr bei 0 und bei j, wenn p[j-1] ein Sternchen ist und prev[j-2] wahr ist.
Setze für jeden Buchstaben von s cur[0] auf falsch.
Fülle cur[1..m]: Eine Sternchenzelle ist cur[j-2] oder (das Element stimmt überein und prev[j]); jede andere Zelle ist (das Element stimmt überein) und prev[j-1].
Vertausche 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

Die meisten falschen Antworten entstehen durch den Stern: Was er wiederholt, wie oft und wo er auf nichts passen kann.

Den Stern so viele Buchstaben wie möglich verbrauchen lassen. a*a passt auf aaa, aber ein gieriges a* verbraucht alle drei Buchstaben, und das letzte a passt dann nicht mehr.
dp[i-1][j-2] für eine weitere Wiederholung verwenden. Damit kann ein Stern höchstens einen Buchstaben aufnehmen, also ergibt aa gegen a* false. Bleib in der Spalte des Sterns: dp[i-1][j].
Zeile 0 bis auf die erste Zelle vollständig auf false setzen. Dann schlägt b gegen a*b fehl, weil das b erfordert, dass a* auf das leere Präfix davor passt.
s[i-1] mit dem Stern selbst statt mit seinem Element p[j-2] vergleichen.
* als „beliebigen Text“ behandeln, wie bei Dateinamensmustern. Hier wiederholt es nur das Element davor; beliebiger Text ist .*.
Eine teilweise Übereinstimmung akzeptieren. t.e passt auf den Anfang von tree, aber die Antwort ist false, weil ein Buchstabe übrig bleibt.
cur[0] = false in der Version mit zwei Zeilen vergessen. Nach dem ersten Tausch enthält cur[0] den true-Wert der Basiszeile.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des Abgleichs mit regulären Ausdrücken?

Die Tabellenlösung benötigt O(n × m) Zeit, wobei n die Länge von s und m die Länge von p ist, 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). Einfache Rekursion kann bei Mustern mit vielen Sternchen exponentielle Laufzeit haben.

Warum liest eine Sternzelle die Zelle darüber und nicht die diagonal gelegene Zelle?

Die Zelle darüber, dp[i-1][j], folgt demselben Muster mit einem Buchstaben weniger von s, und der Stern ist noch enthalten. Nachdem der Stern also s[i-1] verschlungen hat, kann er auch s[i-2] verschlingen und so weiter nach oben in der Spalte. Die diagonal angeordnete Zelle dp[i-1][j-2] entfernt den Stern nach einem Buchstaben, wodurch genau eine Kopie statt beliebig vieler möglich ist.

Wie unterscheidet sich das vom Abgleichen mit Platzhaltern?

Beim Abgleich mit Platzhaltern steht * wie bei Dateinamensmustern für sich allein und passt auf eine beliebige Folge von Zeichen, und ? passt auf ein Zeichen. Hier wiederholt * nur das Element davor, und das Muster für beliebigen Text ist .*. Beide werden mithilfe einer Tabelle über Präfixe gelöst, aber der Stern-Übergang unterscheidet sich: Beim Abgleich mit Platzhaltern werden dp[i][j-1] oder dp[i-1][j] gelesen.

Warum nicht die Regex-Bibliothek der Sprache verwenden?

Ein Interviewer möchte den Algorithmus sehen, nicht den Aufruf einer Bibliotheksfunktion. Außerdem besteht ein echtes Risiko: Viele Regex-Engines arbeiten mit Backtracking, also der langsamen Rekursion des ersten Ansatzes. Ein Muster aus zehn Kopien von a* gefolgt von b kann bei einer langen Folge von a-Buchstaben dazu führen, dass eine solche Engine minutenlang läuft. Die Tabelle wird immer in O(n × m) fertig.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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 Fragen4

Ähnliche Aufgaben