Prüfen, ob zwei Muster übereinstimmen?

Ich habe an meiner Idee von DP gearbeitet und kam mit der untenstehenden Umsetzung des obigen Problems heraus. Bitte zögern Sie nicht, den Code zu bearbeiten, falls jemand einen Testfall als fehlgeschlagen findet. Von meiner Seite habe ich einige Testfälle ausprobiert und alle bestanden, worauf ich unten noch eingehen werde.

Bitte beachten Sie, dass ich die Idee erweitert habe, die zur Lösung des regex -Mustervergleichs mit einer Zeichenkette unter Verwendung von DP verwendet wird. Um auf diese Idee zu verweisen, beziehen Sie sich bitte auf den LeetCode-Link, der im OP zur Verfügung gestellt wird, und schauen Sie sich den Diskussionsteil an. Sie haben die Erklärung für regex matching und die Zeichenfolge angegeben.

Die Idee besteht darin, eine dynamische Memoisierungstabelle zu erstellen, deren Einträge den folgenden Regeln folgen:

1. Wenn Muster1 [i] == Muster2 [j], dp [i] [j] = dp [i-1] [j-1]
2. Wenn Muster1 [i] == '.' oder pattern2 [j] == '.', dann dp [i] [j] = dp [i-1] [j-1]
3. Der Trick liegt hier: Wenn pattern1 [i] = '*', dann wenn dp [i-2] [j] existiert, dann dp [i] [j] = dp [i-2] [j] || dp [i] [j-1] sonst dp [i] [j] = dp [i] [j-1].
4. Wenn pattern2 [j] == '*', dann wenn pattern1 [i] == pattern2 [j-1], dann dp [i] [j] = dp [i] [j-2] || dp [i-1] [j] sonst dp [i] [j] = dp [i] [j-2]

pattern1 wird zeilenweise und pattern2 wird spaltenweise ausgeführt. Beachten Sie auch, dass dieser Code auch für das normale Regex-Muster verwendet werden sollte, das mit einer gegebenen Zeichenfolge übereinstimmt. Ich habe es verifiziert, indem ich es auf LeetCode ausgeführt habe und es dort alle verfügbaren Testfälle bestanden hat!

Unten ist die vollständige Arbeitsimplementierung der obigen Logik:

Treibermethode:

Zeitkomplexität: O(mn) wobei m und n Längen von zwei angegebenen Regex-Mustern sind. Gleiches wird die Komplexität des Raums sein.

Hier ist ein Ansatz, der in polynomieller Zeit funktioniert. Es ist leicht schwer und es könnte eine effizientere Lösung geben.

Die erste Beobachtung, die meiner Meinung nach hier hilft, ist, das Problem neu zu definieren. Anstatt zu fragen, ob diese Muster einander entsprechen , stellen wir uns diese äquivalente Frage:

  

Bei den gegebenen Mustern P1 und P2 gibt es einen String w, wobei P1 und P2 jeweils mit w

übereinstimmen

Mit anderen Worten, anstatt zu versuchen, die beiden Muster zueinander in Übereinstimmung zu bringen, suchen wir nach einer Zeichenfolge, die mit jedem Muster übereinstimmt.

Sie haben vielleicht bemerkt, dass die Arten von Mustern, mit denen Sie arbeiten dürfen, eine Teilmenge der regulären Ausdrücke sind. Dies ist hilfreich, da es eine ziemlich ausgeklügelte Theorie dessen gibt, was Sie mit regulären Ausdrücken und ihren Eigenschaften tun können. Also, anstatt auf Ihr ursprüngliches Problem zu zielen, lassen Sie uns dieses noch allgemeinere lösen:

  

Gibt es zwei reguläre Ausdrücke R1 und R2, gibt es eine Zeichenfolge w, die sowohl mit R1 als auch mit R2 übereinstimmt?

Der Grund für die Lösung dieses allgemeineren Problems ist, dass es uns ermöglicht, die Theorie zu verwenden, die um reguläre Ausdrücke entwickelt wurde. Zum Beispiel können wir in der formalen Sprachtheorie über die -Sprache eines regulären Ausdrucks sprechen, die die Menge aller Zeichenfolgen ist, die die Regex anpasst. Wir können dieses L (R) bezeichnen. Wenn es eine Zeichenfolge gibt, der zwei Regexes R1 und R2 entsprechen, dann gehört diese Zeichenfolge sowohl zu L (R1) als auch zu L (R2). Unsere Frage entspricht also

  

Wenn zwei Regexes R1 und R2 gegeben sind, gibt es einen String w in L (R1) ∩ L (R2)?

Bisher haben wir nur das Problem neu definiert, das wir lösen wollen. Jetzt lass uns es lösen.

Der Schlüsselschritt hier ist, dass es möglich ist, jeden regulären Ausdruck in einen NFA (einen nichtdeterministischen endlichen Automaten) umzuwandeln, so dass jede durch die Regex übereinstimmende Zeichenkette vom NFA akzeptiert wird und umgekehrt. Noch besser, der resultierende NFA kann in Polynomialzeit konstruiert werden. Beginnen wir mit der Erstellung von NFAs für jeden Eingabe-Regex.

Nun, da wir diese NFAs haben, wollen wir diese Frage beantworten: Gibt es eine Zeichenfolge, die beide NFA akzeptieren? Und zum Glück gibt es einen schnellen Weg, dies zu beantworten. Es gibt eine gemeinsame Konstruktion von NFAs, die Produktkonstruktion genannt wird, die bei zwei NFAs N1 und N2 ein neues NFA N 'erstellt, das alle von N1 und N2 akzeptierten Strings und keine anderen Strings akzeptiert. Auch diese Konstruktion läuft in polynomieller Zeit.

Sobald wir N haben, sind wir im Grunde fertig! Alles, was wir tun müssen, ist eine Breiten- oder Tiefensuche durch die Zustände von N ', um zu sehen, ob wir einen akzeptierenden Zustand finden. Wenn ja, großartig! Das heißt, es gibt eine von N 'akzeptierte Zeichenkette, was bedeutet, dass eine Zeichenkette sowohl von N1 als auch von N2 akzeptiert wird, was bedeutet, dass es eine Zeichenkette gibt, die sowohl mit R1 als auch mit R2 übereinstimmt, also lautet die Antwort auf die ursprüngliche Frage "ja!" Und umgekehrt, wenn wir keinen akzeptierenden Zustand erreichen können, lautet die Antwort "Nein, das ist nicht möglich."

Ich bin mir sicher, dass es eine Möglichkeit gibt, all dies implizit zu tun, indem man eine Art implizites BFS über den Automaten N 'ausführt, ohne es tatsächlich zu konstruieren, und es sollte möglich sein, dies in einer Zeit O (n <) zu tun sup> 2 ). Wenn ich noch etwas Zeit habe, werde ich diese Antwort noch einmal durchgehen und darüber nachdenken, wie das geht.

Sie können einen dynamischen Ansatz verwenden, der auf diese Teilmenge eines Thompson-NFA -Strex-Regex zugeschnitten ist und nur% co_de implementiert % und . :

Sie können das entweder mit dynamischer Programmierung (hier in Ruby) tun:

Oder rekursiv:

In jedem Fall:

1. Der operative Startpunkt in der Zeichenfolge und im Muster ist das zweite Zeichen, das nach * sucht und ein Zeichen zurückgibt, solange * mit dem Zeichen in s vor p übereinstimmt.
2. Das Metazeichen * wird als Füllung für das tatsächliche Zeichen verwendet. Dadurch kann jedes Zeichen in . mit s in . übereinstimmen.

Sie können dies auch mit Backtracking lösen, nicht sehr effizient (weil die Übereinstimmung der gleichen Teilstrings mehrmals neu berechnet werden kann, was durch die Einführung einer Nachschlagetabelle, in der alle nicht übereinstimmenden Strings gespeichert werden, und der Berechnung verbessert werden könnte passiert nur, wenn sie nicht in der Nachschlagetabelle gefunden werden können, aber scheint zu funktionieren (js, der Algorithmus geht davon aus, dass die einfache Regex gültig ist, was bedeutet, dass nicht mit * und keine zwei benachbarten * [Probieren Sie es selbst] ):

Für eine kleine Optimierung könnten Sie zuerst die Zeichenfolgen normalisieren:

Es ist eine weitere Reduzierung der Eingabe möglich: x*.* und .*x* können beide durch .* ersetzt werden. Um die maximale Reduktion zu erhalten, müssten Sie versuchen, so viele Sterne wie möglich neben% zu bewegen. co_de% (also einige Sterne nach links zu bewegen kann besser sein, als alle nach rechts zu bewegen).