Ich habe also versucht, diesen Auftrag den ganzen Tag zu lösen, ich verstehe es einfach nicht.
Die folgende Funktion akzeptiert 2 Strings, wobei der zweite (nicht der erste) möglicherweise * (Sternchen) enthält.
Ein * ist ein Ersatz für eine Zeichenkette (leer, 1 Zeichen oder mehr), es kann erscheinen (nur in s2) einmal, zweimal, mehr oder gar nicht, es kann nicht an ein anderes * (% co_de) angrenzen %), keine Notwendigkeit, das zu überprüfen.
Er gibt true zurück, wenn Strings vom selben Muster sind.
Es muss rekursiv sein, keine Schleifen, statische & amp; globale Variablen.
Kann lokale Variablen & amp; Überladen von Methoden.
Kann nur diese Methoden verwenden: ab**c , charAt(i) , substring(i) , substring(i, j) .
Beispiele:
1: length() ; 2: TheExamIsEasy → true
1: The*xamIs*y ; 2: TheExamIsEasy → true
1: Th*mIsEasy* ; 2: TheExamIsEasy → true
1: * ; 2: TheExamIsEasy → true
1: TheExamIsEasy ; 2: TheExamIsEasy → FALSE
Ich habe versucht, die Zeichen nacheinander mit The*IsHard zu vergleichen, bis ein Sternchen angetroffen wird. Dann überprüfe ich, ob das Sternchen leer ist, indem ich das nächste Zeichen ( charAt ) mit dem Zeichen i+1 an Stelle vergleiche s1 , wenn wahr - Fortsetzung der Rekursion mit i als Zähler für i+1 & amp; s2 als Zähler für i ;
if false - Fortsetzung der Rekursion mit s1 als Zähler für beide.
Fahren Sie fort, bis ein anderes Sternchen gefunden wird oder das Ende der Zeichenfolge.
Ich weiß nicht, mein Gehirn verliert die Spur der Dinge, kann sich nicht konzentrieren, irgendwelche Hinweise / Hinweise ? Bin ich in die richtige Richtung?
Es wurde auch gesagt, dass eine Backtracking Technik verwendet werden soll, um dies zu lösen.
Mein Code bisher (macht den Job nicht, auch nicht theoretisch):
%Vor%Hier ist ein Python "psudocode", der helfen kann
%Vor%Hier ist eine grobe Anleitung zum Konvertieren des Codes
%Vor%Das Problem mit Ihrem derzeitigen Ansatz besteht darin, dass nicht alle möglichen Teilstrings berücksichtigt werden, die a * erfüllen kann. Zum Beispiel sollte samePattern ("ababababab", "a * b") wahr zurückgeben; Das * kann alle bis auf den ersten und letzten Buchstaben der Zeichenfolge enthalten, aber Ihr Code geht davon aus, dass das * mit der leeren Zeichenfolge übereinstimmt, da der folgende Buchstabe b ist.
Ich schlage vor, samePattern als "konsumieren" seiner zwei Eingabezeichenfolgen zu betrachten, da es nach einer Übereinstimmung sucht. Bei jedem Schritt sollte samePattern nur das erste Zeichen jeder Zeichenfolge prüfen, um zu entscheiden, ob eine Übereinstimmung am ersten Zeichen möglich ist, und wenn dies der Fall ist, einen rekursiven Aufruf durchführen, um den Rest der Zeichenfolge zu überprüfen . Der Trick wird sein zu wissen, was zu tun ist, wenn Sie ein * in der Musterzeichenfolge erreichen, da es möglicherweise verwendet wird, um das erste Zeichen in s1 anzupassen. Sie sollten nicht den Rest der Zeichenfolge betrachten müssen, um zu entscheiden, was zu tun ist.
Da es sich um Hausaufgaben handelt, überlege ich, was genau dort passiert, aber hoffentlich bringt dich das auf den richtigen Weg.
Hier ist Beispiellösung in c # geschrieben. Entschuldigung für fehlende Kommentare, aber ich hatte keine Zeit für sie: / Wenn Sie sie morgen noch brauchen, dann kann ich etwas schreiben, aber ich hoffe, Sie werden die Idee greifen.
%Vor%Wenn man sich mit Algorithmen wie diesem beschäftigt, lohnt es sich oft, das Problem in kleine Stücke im Kopf zu zerlegen.
Denken Sie beim String-Parsing die Lösung zeichenweise nach. Da Sie keine Kontrolle über die tatsächliche Größe dieser Zeichenfolgen haben, beschränken Sie sich darauf, immer nur das erste Zeichen der Zeichenfolge zu berücksichtigen. (gut - mit einer Ausnahme)
Sobald Sie festgestellt haben, dass die Charaktere, mit denen Sie es zu tun haben, weitere Untersuchungen des Rests der Zeichenfolge erfordern, werfen sie weg ; sie herumzuhalten erhöht nur die Komplexität, warum also die Mühe machen? (Umgekehrt, wenn die Zeichen nicht übereinstimmen, sind Sie fertig - richtig?)
Natürlich ist dies eine Rekursion für Strings, also müssen Sie einige Bedingungen für Fehler / Erfolg haben, die sich auf den Gesamtzustand der Strings beziehen - aber das sind nicht die Probleme - überprüfen der Zustand der Zeichenfolge am oberen Rand der Funktion und weitermachen.
Ich habe einen Algorithmus, den ich aufgepeitscht habe (11 Zeilen Code plus Klammern), den ich posten kann, wenn Sie eine vollständige Lösung haben wollen - aber ich war mir nicht sicher, ob Sie den Algorithmus erhalten wollten, oder nur Zeiger.
Tags und Links string java recursion wildcard backtracking