Einführung
In diesem Lab lernen Sie, wie Sie in Java prüfen können, ob ein String ein Palindrom ist. Wir werden verschiedene Ansätze untersuchen, beginnend mit der grundlegenden Methode, einen String umzukehren und ihn mit dem Original zu vergleichen.
Basierend auf diesem Wissen werden Sie dann eine effizientere Technik mithilfe des Zwei-Zeiger-Ansatzes (two-pointer approach) lernen. Schließlich werden wir unsere Palindromprüfung verbessern, um Groß- und Kleinschreibung sowie nicht-alphabetische Zeichen zu ignorieren, wodurch die Prüfung robuster wird.
String umkehren und vergleichen
In diesem Schritt werden wir beginnen, ein einfaches Java-Programm zu erstellen, das einen String umkehrt und ihn dann mit dem Originalstring vergleicht. Dies ist ein grundlegender Schritt zum Verständnis der String-Manipulation in Java und dient als Baustein für die Prüfung, ob ein String ein Palindrom ist.
Zunächst erstellen wir eine neue Java-Datei. Klicken Sie im Dateiexplorer auf der linken Seite der WebIDE mit der rechten Maustaste im Verzeichnis ~/project, wählen Sie "Neue Datei" und benennen Sie sie StringReverse.java.
Öffnen Sie jetzt die Datei StringReverse.java im Editor und fügen Sie den folgenden Code hinzu:
public class StringReverse {
public static void main(String[] args) {
String originalString = "hello";
String reversedString = "";
// Loop through the original string from end to beginning
for (int i = originalString.length() - 1; i >= 0; i--) {
// Append each character to the reversedString
reversedString += originalString.charAt(i);
}
System.out.println("Original string: " + originalString);
System.out.println("Reversed string: " + reversedString);
// Compare the original and reversed strings
if (originalString.equals(reversedString)) {
System.out.println("The string is the same forwards and backwards.");
} else {
System.out.println("The string is NOT the same forwards and backwards.");
}
}
}
Lassen Sie uns diesen Code analysieren:
String originalString = "hello";: Wir deklarieren eineString-Variable namensoriginalStringund weisen ihr den Wert "hello" zu.String reversedString = "";: Wir deklarieren eine leereString-Variable namensreversedString. Hier werden wir den umgekehrten String erstellen.for (int i = originalString.length() - 1; i >= 0; i--): Dies ist einefor-Schleife, die beim letzten Zeichen desoriginalString(Indexlength() - 1) beginnt und bis zum ersten Zeichen (Index 0) geht.reversedString += originalString.charAt(i);: Innerhalb der Schleife ruftoriginalString.charAt(i)das Zeichen am aktuellen Indexiab. Wir hängen dann dieses Zeichen an denreversedStringan.System.out.println(...): Diese Zeilen geben den Original- und den umgekehrten String in die Konsole aus.if (originalString.equals(reversedString)): Dieseif-Anweisung vergleicht denoriginalStringund denreversedStringmithilfe derequals()-Methode. In Java sollten Sieequals()verwenden, um den Inhalt von Strings zu vergleichen, nicht den==-Operator.- Die
if- undelse-Blöcke geben unterschiedliche Nachrichten aus, je nachdem, ob die Strings gleich sind.
Speichern Sie die Datei StringReverse.java (Strg+S oder Cmd+S).
Öffnen Sie jetzt das Terminal unten in der WebIDE. Stellen Sie sicher, dass Sie sich im Verzeichnis ~/project befinden. Wenn nicht, geben Sie cd ~/project ein und drücken Sie die Eingabetaste.
Kompilieren Sie den Java-Code mit dem Befehl javac:
javac StringReverse.java
Wenn keine Fehler auftreten, wird im Verzeichnis ~/project eine Datei namens StringReverse.class erstellt.
Führen Sie schließlich das kompilierte Java-Programm mit dem Befehl java aus:
java StringReverse
Sie sollten eine Ausgabe ähnlich der folgenden sehen:
Original string: hello
Reversed string: olleh
The string is NOT the same forwards and backwards.
In diesem Fall ist "hello" nicht vorwärts und rückwärts gleich, also erkennt das Programm dies korrekt.
Verwenden des Zwei-Zeiger-Ansatzes (Two-Pointer Approach) für Palindrome
Im vorherigen Schritt haben wir den gesamten String umgekehrt, um zu prüfen, ob er ein Palindrom ist. Obwohl dies funktioniert, erfordert es die Erstellung eines neuen Strings, was für sehr lange Strings ineffizient sein kann. Ein effizienterer Ansatz ist die Verwendung der Zwei-Zeiger-Technik (Two-Pointer Technique).
Die Zwei-Zeiger-Technik beinhaltet die Verwendung von zwei Zeigern (Variablen, die Indexpositionen halten), die an verschiedenen Enden des Strings beginnen und sich zum Zentrum hin bewegen. Wir vergleichen die Zeichen an diesen Zeigern. Wenn sie immer gleich sind, während sich die Zeiger nach innen bewegen, ist der String ein Palindrom. Wenn wir einen Unterschied finden, ist es kein Palindrom.
Erstellen wir ein neues Java-Programm, um dies zu implementieren. Im Dateiexplorer auf der linken Seite erstellen Sie eine neue Datei namens PalindromeChecker.java im Verzeichnis ~/project.
Öffnen Sie PalindromeChecker.java und fügen Sie den folgenden Code hinzu:
public class PalindromeChecker {
public static void main(String[] args) {
String testString = "madam"; // Let's test with a palindrome
boolean isPalindrome = checkPalindrome(testString);
if (isPalindrome) {
System.out.println("\"" + testString + "\" is a palindrome.");
} else {
System.out.println("\"" + testString + "\" is not a palindrome.");
}
testString = "racecar"; // Another palindrome
isPalindrome = checkPalindrome(testString);
if (isPalindrome) {
System.out.println("\"" + testString + "\" is a palindrome.");
} else {
System.out.println("\"" + testString + "\" is not a palindrome.");
}
testString = "hello"; // Not a palindrome
isPalindrome = checkPalindrome(testString);
if (isPalindrome) {
System.out.println("\"" + testString + "\" is a palindrome.");
} else {
System.out.println("\"" + testString + "\" is not a palindrome.");
}
}
// Method to check if a string is a palindrome using two pointers
public static boolean checkPalindrome(String str) {
// Initialize two pointers
int left = 0; // Pointer starting from the beginning
int right = str.length() - 1; // Pointer starting from the end
// Loop while the left pointer is less than the right pointer
while (left < right) {
// Compare characters at the left and right pointers
if (str.charAt(left) != str.charAt(right)) {
// If characters don't match, it's not a palindrome
return false;
}
// Move the pointers inwards
left++;
right--;
}
// If the loop completes without finding any mismatch, it's a palindrome
return true;
}
}
Hier ist, was im neuen Code passiert:
- Wir haben eine separate Methode namens
checkPalindromeerstellt, die einenStringals Eingabe nimmt und einenbooleanzurückgibt (true, wenn es ein Palindrom ist, false sonst). Dies macht unseren Code organisierter und wiederverwendbar. - Innerhalb von
checkPalindromeinitialisieren wirleftauf 0 (der Index des ersten Zeichens) undrightaufstr.length() - 1(der Index des letzten Zeichens). - Die
while (left < right)-Schleife läuft so lange, wie der linke Zeiger links vom rechten Zeiger ist. if (str.charAt(left) != str.charAt(right))vergleicht die Zeichen an den aktuellenleft- undright-Positionen. Wenn sie unterschiedlich sind, wissen wir sofort, dass es kein Palindrom ist, und gebenfalsezurück.- Wenn die Zeichen übereinstimmen, bewegen wir die Zeiger nach innen:
left++erhöht den linken Zeiger, undright--verringert den rechten Zeiger. - Wenn die Schleife ohne Rückgabe von
falseendet, bedeutet dies, dass alle verglichenen Zeichen übereinstimmten, also ist der String ein Palindrom, und wir gebentruezurück. - In der
main-Methode rufen wircheckPalindromemit verschiedenen Teststrings auf und geben die Ergebnisse aus.
Speichern Sie die Datei PalindromeChecker.java.
Jetzt kompilieren und führen Sie das Programm im Terminal aus:
javac PalindromeChecker.java
java PalindromeChecker
Sie sollten die folgende Ausgabe sehen:
"madam" is a palindrome.
"racecar" is a palindrome.
"hello" is not a palindrome.
Dies zeigt, wie der Zwei-Zeiger-Ansatz effizient Palindrome prüft, ohne den gesamten String umzukehren.
Groß- und Kleinschreibung sowie Nicht-Buchstaben in Palindromen ignorieren
Im vorherigen Schritt hat unser Palindromprüfer für einfache Strings wie "madam" und "racecar" funktioniert. In der realen Welt werden bei Palindromen jedoch oft Groß- und Kleinschreibung sowie Satzzeichen ignoriert. Beispielsweise wird "A man, a plan, a canal: Panama" als Palindrom betrachtet.
In diesem Schritt werden wir unseren PalindromeChecker erweitern, um diese Fälle zu behandeln, indem wir Nicht-Buchstaben ignorieren und Groß- und Kleinbuchstaben gleich behandeln.
Öffnen Sie die Datei PalindromeChecker.java im WebIDE-Editor. Wir werden die Methode checkPalindrome ändern.
Ersetzen Sie die vorhandene checkPalindrome-Methode durch die folgende aktualisierte Version:
// Method to check if a string is a palindrome using two pointers,
// ignoring case and non-letter characters
public static boolean checkPalindrome(String str) {
// Initialize two pointers
int left = 0; // Pointer starting from the beginning
int right = str.length() - 1; // Pointer starting from the end
// Loop while the left pointer is less than the right pointer
while (left < right) {
// Move left pointer past non-letter characters
while (left < right && !Character.isLetter(str.charAt(left))) {
left++;
}
// Move right pointer past non-letter characters
while (left < right && !Character.isLetter(str.charAt(right))) {
right--;
}
// If left and right pointers haven't crossed and characters don't match (ignoring case)
if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) {
// If characters don't match, it's not a palindrome
return false;
}
// Move the pointers inwards
left++;
right--;
}
// If the loop completes without finding any mismatch, it's a palindrome
return true;
}
Hier sind die Änderungen, die wir vorgenommen haben:
- Wir haben zwei
while-Schleifen innerhalb der Haupt-while (left < right)-Schleife hinzugefügt. - Die erste innere
while-Schleife (while (left < right && !Character.isLetter(str.charAt(left)))) bewegt denleft-Zeiger vorwärts, solange er noch links vomright-Zeiger ist und das Zeichen amleft-Zeiger kein Buchstabe ist (!Character.isLetter(...)). - Die zweite innere
while-Schleife (while (left < right && !Character.isLetter(str.charAt(right)))) bewegt denright-Zeiger rückwärts, solange er noch links vomright-Zeiger ist und das Zeichen amright-Zeiger kein Buchstabe ist. - Der Vergleich
if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right)))beinhaltet jetzt zwei wichtige Prüfungen:left < right: Dies stellt sicher, dass wir nur Zeichen vergleichen, wenn die Zeiger nach dem Überspringen von Nicht-Buchstaben nicht übereinandergelaufen sind.Character.toLowerCase(...): Dies wandelt beide Zeichen in Kleinbuchstaben um, bevor sie verglichen werden, wodurch die Groß- und Kleinschreibung effektiv ignoriert wird.
- Wenn die Zeichen (nach der Umwandlung in Kleinbuchstaben) nicht übereinstimmen, geben wir
falsezurück. - Wenn sie übereinstimmen, bewegen wir beide Zeiger nach innen (
left++,right--), um das nächste Zeichenpaar zu prüfen.
Jetzt ändern wir die main-Methode, um mit einem String zu testen, der Leerzeichen, Satzzeichen und gemischte Groß- und Kleinschreibung enthält. Ersetzen Sie die vorhandenen Testfälle in der main-Methode durch Folgendes:
public static void main(String[] args) {
String testString = "A man, a plan, a canal: Panama"; // A classic palindrome
boolean isPalindrome = checkPalindrome(testString);
if (isPalindrome) {
System.out.println("\"" + testString + "\" is a palindrome.");
} else {
System.out.println("\"" + testString + "\" is not a palindrome.");
}
testString = "No 'x' in Nixon"; // Another palindrome
isPalindrome = checkPalindrome(testString);
if (isPalindrome) {
System.out.println("\"" + testString + "\" is a palindrome.");
} else {
System.out.println("\"" + testString + "\" is not a palindrome.");
}
testString = "hello world"; // Not a palindrome
isPalindrome = checkPalindrome(testString);
if (isPalindrome) {
System.out.println("\"" + testString + "\" is a palindrome.");
} else {
System.out.println("\"" + testString + "\" is not a palindrome.");
}
}
Speichern Sie die Datei PalindromeChecker.java.
Kompilieren und führen Sie das aktualisierte Programm im Terminal aus:
javac PalindromeChecker.java
java PalindromeChecker
Sie sollten jetzt die folgende Ausgabe sehen, die die Palindrome auch bei Nicht-Buchstaben und gemischter Groß- und Kleinschreibung korrekt identifiziert:
"A man, a plan, a canal: Panama" is a palindrome.
"No 'x' in Nixon" is a palindrome.
"hello world" is not a palindrome.
Sie haben Ihren Palindromprüfer erfolgreich erweitert, um komplexere Strings zu behandeln!
Zusammenfassung
In diesem Lab haben wir gelernt, wie man in Java prüft, ob ein String ein Palindrom ist. Wir haben begonnen, indem wir eine Methode implementiert haben, um einen String umzukehren und ihn mit dem ursprünglichen String zu vergleichen, um festzustellen, ob es sich um ein Palindrom handelt. Dies beinhaltete das Erstellen einer Java-Datei, das Schreiben von Code, um den String rückwärts zu durchlaufen, und die Verwendung der equals()-Methode für den Vergleich.
Anschließend haben wir den Zwei-Zeiger-Ansatz (Two-Pointer Approach) untersucht, eine effizientere Methode zur Palindromprüfung, die die Erstellung eines neuen umgekehrten Strings vermeidet. Schließlich haben wir unsere Palindromprüfung erweitert, um Groß- und Kleinschreibung sowie Nicht-Buchstaben zu ignorieren, wodurch die Prüfung robuster für reale Szenarien wird.
