Wie man prüft, ob ein String in Java ein Palindrom ist

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.

Skills Graph

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 eine String-Variable namens originalString und weisen ihr den Wert "hello" zu.
• String reversedString = "";: Wir deklarieren eine leere String-Variable namens reversedString. Hier werden wir den umgekehrten String erstellen.
• for (int i = originalString.length() - 1; i >= 0; i--): Dies ist eine for-Schleife, die beim letzten Zeichen des originalString (Index length() - 1) beginnt und bis zum ersten Zeichen (Index 0) geht.
• reversedString += originalString.charAt(i);: Innerhalb der Schleife ruft originalString.charAt(i) das Zeichen am aktuellen Index i ab. Wir hängen dann dieses Zeichen an den reversedString an.
• System.out.println(...): Diese Zeilen geben den Original- und den umgekehrten String in die Konsole aus.
• if (originalString.equals(reversedString)): Diese if-Anweisung vergleicht den originalString und den reversedString mithilfe der equals()-Methode. In Java sollten Sie equals() verwenden, um den Inhalt von Strings zu vergleichen, nicht den ==-Operator.
• Die if- und else-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.

Verwendung 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 checkPalindrome erstellt, die einen String als Eingabe nimmt und einen boolean zurückgibt (true, wenn es ein Palindrom ist, false sonst). Dies macht unseren Code organisierter und wiederverwendbar.
• Innerhalb von checkPalindrome initialisieren wir left auf 0 (der Index des ersten Zeichens) und right auf str.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 aktuellen left- und right-Positionen. Wenn sie unterschiedlich sind, wissen wir sofort, dass es kein Palindrom ist, und geben false zurück.
• Wenn die Zeichen übereinstimmen, bewegen wir die Zeiger nach innen: left++ erhöht den linken Zeiger, und right-- verringert den rechten Zeiger.
• Wenn die Schleife ohne Rückgabe von false endet, bedeutet dies, dass alle verglichenen Zeichen übereinstimmten, also ist der String ein Palindrom, und wir geben true zurück.
• In der main-Methode rufen wir checkPalindrome mit 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 bei Palindromprüfung 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 den left-Zeiger vorwärts, solange er noch links vom right-Zeiger ist und das Zeichen am left-Zeiger kein Buchstabe ist (!Character.isLetter(...)).
• Die zweite innere while-Schleife (while (left < right && !Character.isLetter(str.charAt(right)))) bewegt den right-Zeiger rückwärts, solange er noch links vom right-Zeiger ist und das Zeichen am right-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 false zurü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.