Ich kann nicht herausfinden, wie man das löst:
Gibt zwei Strings an, wobei einer für ein Muster, einer für eine zufällige Zeichenfolge steht, und bestimmen, ob das Muster mit der ersten Zeichenfolge übereinstimmt
ex:
%Vor%string1 und string2 sind also Mustervergleiche
versus wenn String2 "catcatcatcat" wäre, wäre dies kein Mustervergleich.
Mach dies für jedes Muster und jede Zeichenkette.
Ich weiß, es ist Rekursion, aber ich bin ziemlich fest auf ... wie man das löst
Ok, ich werde versuchen, eine Rekursion dafür zu erklären, klingt richtig, aber ich habe keine Gelegenheit, es zu testen (nicht zu Hause).
Nimm einen Vektor v ['Größe des Alphabets'], wobei v [i] = wie viele Buchstaben von String2 = Buchstabe i von String 1 ist.
In Ihrem Fall ist es am Ende: v ['a'] = 3, v [b] = 3;
Sie initialisieren den Vektor mit 1.
Für die rec-Funktion:
Sie nehmen den ersten Buchstaben von string1: a; Repräsentieren für eine from string2 ist die Zeichenfolge, die bei string2 beginnt und bei string2 + v ['a'] endet; was ist "c"; Sie prüfen, ob dies bis jetzt eine gültige Lösung ist, und das ist es.
Dann gehst du in rec (string1 + 1), Buchstabe a wieder, Da v ['a'] immer noch = 1 ist, nimmst du das zweite ein as = 'a'. Sie überprüfen, ob es sich um eine gültige Soulution handelt, und nicht, weil Sie das erste a bereits als 'c' definiert haben. Du gehst zurück in die Rekursion und erhöhst v ['a'], beginne vom Betteln.
Sie nehmen den ersten Buchstaben von string1: a; Stellen Sie aus string2, das ist "ca", (jetzt v ['a'] = 2) Überprüfen Sie, ob sie gültig sind. rec (string1 +1);
und so weiter ... an einem Punkt wirst du v ['a'] = 3 und v ['b'] = 3 erreichen; dann mit der Rec-Funktion finden Sie die Lösung.
Ich für meinen Teil finde es einfacher, sie in einer interativen Funktion zu implementieren, aber Sie haben etwas über Rekursion gesagt, also ja.
Nimm die Anzahl der eindeutigen Buchstaben. Dann wollen Sie alle Kombinationen von möglichen Längen für jeden Buchstaben mit den folgenden Einschränkungen durchlaufen:
Das heißt, für 2 eindeutige Buchstaben und eine Zeichenkettenlänge von 4 sind die möglichen Längen:
(1, 3) und (2, 2)
Von hier ist es einfach. Für jeden eindeutigen Buchstaben können Sie die Zeichenkette herausfinden, die der Buchstabe für die gegebene Zeichenkette darstellen muss, da Sie die Länge jedes Buchstabens kennen. Dann ist es wichtig, jeden Buchstaben der Zeichenkette zuzuordnen, die er darstellen muss, und wenn ein Buchstabe zu irgendeinem Zeitpunkt einer Zeichenkette entspricht, die nicht mit einer früheren Instanz übereinstimmt, dann haben Sie keine Übereinstimmung.
Für Ihr Beispiel:
%Vor%Hier für die Iteration, wo die Längen (3, 3) sind. Da wir eine Länge von 3 kennen, kennen wir die erste Iteration eines Muss "Katze". Dann entspricht das nächste a "Katze" (habe noch eine Übereinstimmung). Dann müssen die nächsten 3 b entsprechen. Dies ist das erste b, so dass es alle 3 Zeichen zuordnen kann. Dann passe am Ende wieder eine Katze an, und du bist fertig.
Wenn Sie möchten, dass a, b, c wie im @MartijnCourteaux-Kommentar (und in Ihrer Frage, die ich jetzt wieder lese) beschrieben eindeutig sind, dann können Sie am Ende einfach Ihre Karte auf gemeinsame Werte prüfen, falls es welche gibt gemeinsame Werte dann haben Sie keine Übereinstimmung.
Wenn Sie bei einer Iteration eine Übereinstimmung haben, stimmt die Zeichenfolge mit dem Muster überein. Es gibt nur keine Übereinstimmung, wenn es bei ALLEN Iterationen keine Übereinstimmung gibt.
Das ist ziemlich einfach zu erreichen:
Regex ist der Weg zu gehen. In Regex gibt es eine sogenannte Rückreferenz . Backreferences müssen mit derselben Zeichenfolge übereinstimmen, da die angegebene Match-Gruppe bereits übereinstimmt. d. h., die Regex ^([ab])\1$ wird jeder Zeichenfolge wie aa oder bb entsprechen. Die erste Gruppe stimmt entweder mit a oder b überein - aber die Rückreferenz benötigt die gleiche Übereinstimmung, die Matchgroup (in diesem Fall "1") stimmt überein.
Alles, was Sie tun müssen, ist: Konvertieren Sie Ihr String-basiertes Muster in ein Regex-Muster.
Beispiel:
%Vor%erzeugt:
%Vor%Dies wird GENAU mit Ihrer gegebenen Zeichenfolge "catcatdogcat" übereinstimmen, während die Gruppe 1 "Katze" ist und die Gruppe 2 "Hund" ist.
Was Sie jetzt tun müssen, ist:
aaba char durch char. ([a-z]+) und notiere die Nummer dieser Matchgroup (Array, Hashmap, ...) \1 (wenn die aufgezeichnete Nummer für den Brief 1 war) ^ und $ . Schließlich wird Ihre Zeichenfolge aaba in ^([a-z]+)\1([a-z]+)\1$ konvertiert und Ihren Anforderungen entsprechend ausgeführt. Das Muster abccba wird zum Regex ^([a-z]+)([a-z]+)([a-z]+)\3\2\1$
Verwenden Sie abschließend den Matcher, um die angegebene Zeichenfolge zu überprüfen.
In diesem Beispiel werden nur Kleinbuchstaben angenommen, aber Sie können es erweitern.
es ist jedoch wichtig, das "+" zu behalten, denn das "*" würde Null-Länge-Übereinstimmungen zulassen, wodurch Ihre Regex ungefähr die ganze Zeit übereinstimmen wird.
Zweites Beispiel:
%Vor%erzeugt:
%Vor%edit: wenn nötig (auch wenn es nicht zu 100% Ihren Anforderungen entspricht - siehe Kommentare):
%Vor%