Java: Wie wird der Wildcard-Abgleich implementiert?

Question

Ich bin die Erforschung, wie k-Werte in der BST zu finden, die das Ziel am nächsten sind, und kam über die folgende Umsetzung mit den Regeln ‚?‘

Entspricht einem einzelnen Zeichen.

'*' Entspricht einer beliebigen Zeichenfolge (einschließlich der leeren Sequenz).

Die Übereinstimmung sollte die gesamte Eingabezeichenfolge abdecken (nicht teilweise).

sollte Der Funktionsprototyp sein: Bool IsMatch (const char * s, const char * p)

Einige Beispiele:

IsMatch ("aa", "a") → falsche

IsMatch ("aa", "aa") → wahre

IsMatch ("aaa", "aa") → falsch

IsMatch ("aa", "*") → wahr

IsMatch ("aa", "a *") → wahre

IsMatch ("ab", "*?") → wahre

IsMatch ("aab", „c a b „) → falsch

Code:

import java.util.*; 

public class WildcardMatching { 
    boolean isMatch(String s, String p) { 
     int i=0, j=0; 
     int ii=-1, jj=-1; 

     while(i<s.length()) { 
      if(j<p.length() && p.charAt(j)=='*') { 
       ii=i; 
       jj=j; 
       j++; 
      } else if(j<p.length() && 
         (s.charAt(i) == p.charAt(j) || 
         p.charAt(j) == '?')) { 
       i++; 
       j++; 
      } else { 
       if(jj==-1) return false; 

       j=jj; 
       i=ii+1; 
      } 
     } 

     while(j<p.length() && p.charAt(j)=='*') j++; 

     return j==p.length(); 
    } 

    public static void main(String args[]) { 
     String s = "aab"; 
     String p = "a*"; 

     WildcardMatching wcm = new WildcardMatching(); 
     System.out.println(wcm.isMatch(s, p)); 
    } 
} 

und meine Frage ist, was ist der Grund für zwei zusätzliche Indizes mit, ii und 012., und warum werden sie mit -1 initialisiert? Was ist der Zweck von jedem? Würde es nicht mit i und j genug sein?

Und was ist der Zweck der ii=i; und jj=j; im ersten Fall, wenn, und i=ii+1; und j=jj; im dritten wenn Fall?

Schließlich, in welchem ​​Fall würden Sie auf while(j<p.length() && p.charAt(j)=='*') j++; stoßen?

Beispiele wären extrem hilfreich beim Verständnis. Vielen Dank im Voraus und akzeptieren die Antwort/Abstimmung.

Answer 1

Es sieht aus wie ii und jj werden verwendet, um den Platzhalter "*" zu behandeln, der mit jeder Sequenz übereinstimmt. Ihre Initialisierung auf -1 wirkt wie eine Markierung: Sie sagt uns, ob wir eine nicht übereinstimmende Sequenz getroffen haben und derzeit kein "*" auswerten. Wir können Ihre Beispiele einzeln durchgehen.

Beachten Sie, dass i den Parameter in Beziehung steht s (die ursprüngliche Zeichenfolge) und j wird auf den Parameter p (das Muster) verwendet.

isMatch("aa","a"): diese gibt false zurück, weil die j<p.length() Anweisung fehl, bevor wir die while-Schleife verlassen, da die Länge der p („a“) ​​ist nur 1, während die Länge der s („aa“) 2 ist, so Wir werden zum else Block springen. Hier kommt die -1-Initialisierung ins Spiel: Da wir in keine Wildcards gesehen haben, ist jj immer noch -1, was anzeigt, dass die Zeichenfolgen nicht übereinstimmen können, daher geben wir false zurück.

isMatch("aa","aa"): s und p sind genau die gleiche, so dass das Programm wertet wiederholt den else-if-Block ohne Probleme und schließlich bricht aus der while-Schleife einmal i gleich 2 (die Länge von „aa“). Die zweite while-Schleife läuft nie, da nicht weniger als p.length() ist - tatsächlich, da die else-if-Inkremente i und j zusammen sind sie beide gleich 2, und 2 ist nicht kleiner als die Länge von "aa". Wir geben j == p.length() zurück, was 2 == 2 ergibt, und erhalten true.

isMatch("aaa","aa"): dieser scheitert aus dem gleichen Grund wie der erste. Die Zeichenfolgen haben nämlich nicht die gleiche Länge und wir treffen niemals ein Platzhalterzeichen.

isMatch("aa","*"): hier wird es interessant. Zuerst geben wir den if-Block ein, da wir in ein "*" gesehen haben. Wir setzen ii und jj auf 0 und erhöhen nur j. Bei der zweiten Iteration schlägt j<p.length() fehl, also springen wir zum else-Block. jj ist nicht mehr -1 (es ist 0), also setzen wir j auf 0 zurück und setzen i auf 0 + 1. Dies erlaubt uns im Grunde, den Platzhalter weiter zu evaluieren, da j gerade auf jj zurückgesetzt wird, was die Position des Platzhalters enthält, und ii sagt uns, wo wir in unserem ursprünglichen String anfangen sollen. Dieser Testfall erklärt auch die zweite While-Schleife. In einigen Fällen ist unser Muster möglicherweise viel kürzer als die ursprüngliche Zeichenfolge, daher müssen wir sicherstellen, dass es mit Platzhaltern übereinstimmt. Beispiel: isMatch("aaaaaa","a**") sollte "true" zurückgeben, aber die abschließende return-Anweisung überprüft, ob j == p.length(), ob wir das gesamte Muster überprüft haben. Normalerweise würden wir bei der ersten Wildcard anhalten, da sie mit allem übereinstimmt, also müssen wir schließlich den Rest des Musters durchlaufen und sicherstellen, dass es nur Wildcards enthält.

Von hier aus können Sie die Logik hinter den anderen Testfällen herausfinden. Ich hoffe das hat geholfen!

Answer 2

Schauen wir uns das ein bisschen außer Betrieb.

Erstens ist dies eine parallele Iteration der Saite (s) und dem Platzhaltermuster (p), variable i indizieren Verwendung s und variable jp indizieren.

Die Schleife while stoppt die Iteration, wenn das Ende von s erreicht ist. Wenn das passiert, wurde hoffentlich auch das Ende von erreicht, in dem Fall wird true (j==p.length()) zurückgegeben.

Wenn jedoch p mit einem * endet, ist, dass auch gültig (zB isMatch("ab", "ab*")), und das ist, was der while(j<p.length() && p.charAt(j)=='*') j++; Schleife stellt sicher, dh jede * im Muster an diesem Punkt wird übersprungen, und wenn diese erreicht Ende p, dann es gibt true zurück.Wenn das Ende von nicht erreicht wird, wird false zurückgegeben.

Das war die Antwort auf Ihre letzte Frage. Jetzt schauen wir uns die Schleife an. Die else if wird sowohl i als auch j iterieren, solange es eine Übereinstimmung gibt, z. 'a' == 'a' oder 'a' == '?'.

Wenn ein * Platzhalter gefunden wird (erste if), speichert er die aktuellen Positionen in iijj und, falls Rückzieher notwendig wird, dann überspringt das Wildcard-Zeichen.

Dies beginnt im Wesentlichen mit der Annahme, dass der Platzhalter der leeren Zeichenfolge entspricht (z. B. isMatch("ab", "a*b")). Wenn die Iteration fortgesetzt wird, entspricht else if dem Rest, und die Methode endet mit der Rückgabe true.

Nun, wenn eine Diskrepanz gefunden wird (else Block), wird es versuchen, Backtrack. Wenn es keinen gespeicherten Platzhalter (jj==-1) hat, kann es natürlich nicht zurückverfolgen, also gibt es false zurück. Deshalb wird jj auf -1 initialisiert, so dass es erkennen kann, ob ein Platzhalter gespeichert wurde. ii konnte auf alles initialisiert werden, wird jedoch aus Konsistenzgründen auf -1 initialisiert.

Wenn eine Wildcard-Position in ii und jj gespeichert wurde, wird er diese Werte, dann nach vorne i nach der anderen, dh es wird angenommen, dass, wenn das nächste Zeichen gegen die Wildcard abgestimmt ist, der Rest des Anpassungs true erfolgreich sein wird und die Rück wiederherstellen .

Das ist die Logik. Nun könnte es ein kleines bisschen optimiert werden, da dieses Zurückverfolgen nicht optimal ist. Es setzt derzeit j zurück auf die * und i zurück zum nächsten Zeichen. Wenn es umläuft, wird es in den if eingegeben und speichern Sie den Sicherungswert erneut in jj und speichern Sie den i Wert in ii, und erhöhen Sie dann j. Da dies gegeben ist (es sei denn Ende s erreicht ist), könnte der Rückzieher machen nur, dass auch Speichern einer Iterationsschleife, das heißt

} else { 
    if(jj==-1) return false; 

    i=++ii; 
    j=jj+1; 
} 

Answer 3

Der Code Buggy mir aussieht. (Siehe unten)

Der angebliche Zweck von ii und jj ist es, eine Form des Backtracking zu implementieren.

Wenn Sie beispielsweise versuchen, "abcde" mit dem Muster "a * e" abzugleichen, passt der Algorithmus zuerst das "a" im Muster an das "a" in der Eingabezeichenfolge an. Dann wird es eifrig passen Sie das "*" gegen den Rest der Zeichenfolge ... und finden, dass es einen Fehler gemacht hat. An diesem Punkt muss es wieder ansetzen und versuchen, eine alternative

Die ii und jj sind, den Punkt zu erfassen, um einen Rückzieher, und die Verwendungen sind entweder diese Variablen einen neuen Rücksetzpunkt oder Rückzieher der Aufnahme.

Oder zumindest war das wahrscheinlich die Absicht des Autors zu einem bestimmten Zeitpunkt.

Die while(j<p.length() && p.charAt(j)=='*') j++; scheint mit einem Rand-Fall

---

jedoch tun zu werden, ich glaube nicht, dieser Code korrekt ist.

1. Es wird sicherlich nicht mit Backtracking in dem Fall, wo es mehrere "*" Wildcards im Muster gibt. Das erfordert eine rekursive Lösung.

2. Der Teil:

   if(j<p.length() && p.charAt(j)=='*') { 
        ii=i; 
        jj=j; 
        j++; 
   

   macht nicht viel Sinn machen. Ich hätte gedacht, es sollte i nicht j erhöhen. Es kann sich mit dem Verhalten des else-Teils "vermischen", aber selbst wenn dies der Fall ist, ist dies ein verschlungener Weg, dies zu kodieren.

---

Hinweis:

1. Sie diesen Code nicht als Beispiel verwenden. Selbst wenn es (in einem begrenzten Sinne) funktioniert, ist es kein guter Weg, um diese Aufgabe zu erledigen, oder ein Beispiel für Klarheit oder guten Stil.

2. Ich würde damit umgehen, indem Sie das Wildcard-Muster in eine Regex übersetzen und dann Pattern/Matcher verwenden, um die Übereinstimmung zu tun.

   Zum Beispiel: Wildcard matching in Java