Finden aller möglichen Möglichkeiten zum Einfügen eines Musters in eine Zeichenfolge

7

Ich habe eine Weile über dieses Problem nachgedacht und kann nur eine rekursive Lösung finden, aber ich habe das Gefühl, dass es eine dynamische Programmiermethode gibt, ich kann es einfach nicht herausfinden. Ist das ein berühmtes Problem, von dem ich nichts weiß?


F: Geben Sie anhand einer Zeichenfolge und eines Musters die Anzahl der eindeutigen Methoden zum Abgleichen der Buchstaben des Musters (in der angegebenen Reihenfolge) mit der Zeichenfolge zurück.

Erläuterung: Um eine Übereinstimmung zu finden, nehmen Sie das erste Zeichen des Musters, suchen das erste übereinstimmende Zeichen in der Zeichenfolge, nehmen dann das zweite Zeichen des Musters und stimmen mit dem ersten übereinstimmenden Zeichen der Zeichenfolge überein, das NACH Ihrer vorherigen Übereinstimmung liegt Charakter.

Beispiel 1 (4 Übereinstimmungen):

Zeichenfolge: DABBCDDE

Muster: ABD

Mögliche Möglichkeiten (fettgedruckte Zeichen sind der Punkt, an dem das Muster mit der Zeichenfolge übereinstimmt):

  • D AB BC D DE
  • D A B B C D DE
  • D AB BCD D E.
  • D A B B CD D E.

Beispiel 2 (0 Übereinstimmungen):

Zeichenfolge: ABC

Muster: BCA

(Sie stimmen mit B, C überein und befinden sich dann am Ende der Zeichenfolge. Sie können NICHT zurückgehen und mit vorherigen Zeichen übereinstimmen.)


Mit dem rekursiven Ansatz habe ich eine Methode, die verfolgt, an welchem ​​Index ich mich in der Zeichenfolge ( sIndex ) sowie im Muster ( pIndex ) befinde . Wenn die Zeichenfolge [sIndex] mit dem Muster [pIndex] übereinstimmt, rufen wir die Methode erneut auf und erhöhen sIndex und pIndex. Wenn nicht, erhöhen Sie einfach den sIndex und versuchen Sie erneut, eine Übereinstimmung zu finden. Die Methode gibt dann die Gesamtzahl zurück, da der Rückgabewert der rekursiven Aufrufe addiert wird. (Übereinstimmungen addieren 1, keine Übereinstimmungen addieren 0)

Basisfälle:

  • Wenn pIndex größer als die Länge des Musters ist, geben Sie 0 zurück.

  • Wenn sIndex größer als die Länge der Zeichenfolge ist, geben Sie 1 zurück (wir haben eine Übereinstimmung gefunden!)


Welche anderen Lösungen gibt es?

Daniel Olsson
quelle
Sind doppelte Werte im Muster zulässig? Ist garantiert, dass sowohl Muster als auch Zeichenfolge in Ordnung sind?
Brandon Arnold
Ja, doppelte Werte sind im Muster zulässig. Ich weiß nicht, ob ich mich zu klar ausgedrückt habe, aber wenn Sie die Reihenfolge verschlüsseln, ändert sich das Problem. Wenn Sie also CBA als Zeichenfolge haben und das Muster ABC ist, haben Sie keine Übereinstimmungen, da die erste Übereinstimmung das A ist und die Zeichenfolge keine weiteren Zeichen mehr enthält, die mit den verbleibenden Zeichen im Muster (BC) übereinstimmen. Macht es das klar?
Daniel Olsson
Ich finde das insertingziemlich irreführend. Stimmen diese Elemente nicht patternmit den Elementen in der stringrichtigen Reihenfolge überein?
Mai
Meine Regex-Antwort wurde gelöscht, da ich nach dem Spielen auf js fiddle festgestellt habe, dass sie nicht allen möglichen Permutationen entspricht :(
Gavin Clarke
1
Mai, das stimmt, ich werde den Wortlaut ändern.
Daniel Olsson

Antworten:

1

Ich denke, Sie müssen keine dynamische Programmierung verwenden, um dies zu lösen. Ich denke das ist die Lösung:

  1. Erstellen Sie zunächst eine Liste mit Listen, um das Vorkommen von Zeichen im Muster im angegebenen Text beizubehalten.

  2. Es wird so sein

Das folgende Diagramm:

   A    B    D 
             0 
   1 -> 2 -> 5
        3    6 
  1. Dies impliziert (unter der Annahme einer 0-Indexierung), dass A an der 0. Position auftritt, B an 2,3 Positionen auftritt, D an 0,5,6 Positionen auftritt.

  2. Verwenden Sie für jedes der aufeinanderfolgenden Spaltenpaare (hier A, B und B, D) Zeiger, um die entsprechenden Werte in einer Spalte den nächstgrößeren Werten in der nächsten Spalte zuzuordnen. Hier hat 1 (in Spalte 1) einen Zeiger auf 2 (in Spalte 2) und 2 (in Spalte 2) einen Zeiger auf 5 (in Spalte 3), da 0 kleiner als 2 ist. 3 (in Spalte 2) hat einen Zeiger auf 5 (in Spalte 3) ) (Ich konnte hier nicht zeichnen).

  3. Ermitteln Sie für jeden Wert in der ersten Spalte die Anzahl der möglichen Wege mithilfe der Zeiger. Hier 1 -> 2 und 2 -> 5 und somit beträgt die Anzahl der möglichen Wege 2 * 2 Wege (dh 1-> 2-> 5, 1-> 2-> 6, 1-> 3-> 5, 1 -> 3-> 6). Sie müssen nur die Anzahl der verbleibenden Elemente in der Spalte für jeden Wert von A multiplizieren.

  4. Hier ist nur 1 Wert für Spalte 1 (dh A) vorhanden. Wenn mehrere Spalten vorhanden sind, berechnen wir den Wert für jeden Wert von A mithilfe der Zeiger und addieren alle, um die Anzahl der Möglichkeiten zu ermitteln.

  5. Ich denke, die Komplexität ist O (n), da die Konstruktionsliste O (n) ist, der Zeigerraum und die Konstruktionszeit O (n) sind.

kaushalpranav
quelle
Dies ist korrekt, aber Sie müssen die Vorkommen der Musterbuchstaben genauer generieren. Die Komplexität dafür ist O (nm), wobei n die Musterlänge und m die Textlänge ist. (Wir müssen alle Vorkommen jedes Letters im Muster finden).
Adrian Buzea