So habe ich versucht, diese Aufgabe den ganzen Tag zu lösen, kann es einfach nicht bekommen.Rekursive Funktion, um eine Zeichenfolge mit einem Platzhaltermuster zu vergleichen
Die folgende Funktion akzeptiert 2 Strings, die zweite (nicht die erste) möglicherweise enthält *
's (Sternchen).
Ein *
ist ein Ersatz für eine Zeichenfolge (leer, 1 Zeichen oder mehr), kann erscheinen (nur in s2) einmal, zweimal, mehr oder gar nicht, es kann nicht neben einem anderen sein *
(ab**c
), nein muss das überprüfen.
public static boolean samePattern(String s1, String s2)
Es gibt True zurück, wenn Strings das gleiche Muster haben.
Es muss rekursiv sein, keine Schleifen verwenden, statische & globale Variablen. Kann lokale Variablen & Methode Überladung verwenden.
Kann nur diese Methoden verwenden: charAt(i)
, substring(i)
, substring(i, j)
, length()
.
Beispiele:
1: TheExamIsEasy
; 2: The*xamIs*y
→ richtig
1: TheExamIsEasy
; 2: Th*mIsEasy*
→ richtig
1: TheExamIsEasy
; 2: *
→ wahr
1: TheExamIsEasy
; 2: TheExamIsEasy
→ wahr
1: TheExamIsEasy
; 2: The*IsHard
→ FALSE
habe ich versucht, die die Zeichen eines nach dem anderen zu vergleichen charAt
verwenden, bis ein Stern angetroffen wird, dann prüfen, ob der Stern eine leere ist, sukzessive durch den Vergleich char (i+1
) mit dem char von s1
an Position i
, falls wahr - Fortsetzung der Rekursion mit i+1
als Zähler für s2
& i
als Zähler für s1
;
wenn falsch - Fortsetzung der Rekursion mit i+1
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, keine Zeiger/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 (nicht die Arbeit erledigen, auch theoretisch):
public static boolean samePattern(String s1, String s2) {
if (s1.equals(s2) || s2 == "*") {
return true;
}
return samePattern(s1, s2, 1);
}
public static boolean samePattern(String s1, String s2, int i)
{
if (s1.equals(s2))
return true;
if (i == s2.length() - 1) // No *'s found -- not same pattern.
return false;
if (s1.substring(0, i).equals(s2.substring(0, i)))
samePattern(s1, s2, i+1);
else if (s2.charAt(i-1) == '*')
samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings.
else
samePattern(s1.substring(1), s2, i);
}
Kudos für die Umwandlung, und nicht die gesamte Lösung. –