Das Java-Programm zum Überprüfen eines Strings ist ein Palindrom

Manche Probleme in der Programmierung haben den Status von Klassikern. In der Regel beziehen sich solche Aufgaben auf die Mathematik und werden von Studierenden der Fachrichtung Informatik sowie Arbeitssuchenden bei Vorstellungsgesprächen sehr gern gestellt. Sie sind gut, weil sie dabei helfen, Ihr Denken recht gut auf Programmierer-Art aufzubauen und zu trainieren. Eines dieser Probleme ist die Überprüfung, ob eine Zeichenfolge ein Palindrom ist, und wir werden es in diesem Artikel betrachten.

Was ist ein Palindrom und warum kann man danach suchen?

Ein Palindrom ist eine Zahl, eine Buchstabenkombination, ein Wort oder ein Text, der sich in beide Richtungen gleich liest. Zusammenfassend kann man als Palindrom jede Zeichenmenge bezeichnen, die symmetrisch zu ihrer Mitte ist. Das Wort hat seinen Ursprung im Griechischen und bedeutet wörtlich „zurücklaufen“ (palin bedeutet „wieder, zurück“ und dromos „laufen“). Palindrom bedeutet in Java dasselbe wie in der allgemeinen Bedeutung. Beispiele für Palindrome:

• 1881
• aaqquqqaa
• Pop
• Mittag
• eben
• Rotator
• Mein Fitnessstudio
• Frau, ich bin Adam
• Nun, Sir, ein Krieg ist gewonnen!

1881 ist eine Palindromzahl und die anderen sind Palindromzeichenfolgen. In diesem Artikel betrachten wir Palindrome, die als Strings dargestellt werden, aber einige Algorithmen sind durchaus auf andere Arten von Palindromen in Java anwendbar. Warum sollten Sie nach Palindromen suchen? Tatsächlich müssen wir im Alltag nicht oft nach Palindromen suchen. Es ist eine sehr spezifische Aufgabe. Wenn wir uns an String-Algorithmen erinnern, können Programmierer in der Praxis häufiger feststellen, dass sie nach einem Teilstring in einem String suchen und nicht nach Palindromen oder deren Anzahl. Probleme im Zusammenhang mit Palindromen haben jedoch wichtige Anwendungen. Das erste ist die Olympia-Programmierung. Es könnte Aufgaben geben, Palindrome zu identifizieren. Die zweite Anwendung, die für unerfahrene Programmierer relevant ist, ist das Vorstellungsgespräch. Bei einem technischen Vorstellungsgespräch Möglicherweise werden Sie gebeten, schnell ein Programm zu schreiben, um zu überprüfen, ob eine Zeichenfolge ein Palindrom ist, vielleicht sogar auf einem Blatt Papier. Nun, in der Wissenschaft sind biologische Algorithmen die praktischste Anwendung zum Finden von Palindromen. Laut Wikipedia spielt die Palindromizität biologischer Verbindungen eine wichtige Rolle für die Eigenschaften verschiedener biologischer Verbindungen.

Codebeispiel für den Palindrome-Algorithmus

Denken wir nach. Ein String ist eine Folge von Zeichen, man könnte sagen, ein Array von Zeichen. Am logischsten wäre es, diese Reihenfolge von beiden Seiten bis zur Mitte zu verfolgen und die Extremzeichen zu vergleichen. Wenn bis zur Mitte alle unsere Charaktere übereinstimmen, dann haben wir ein Palindrom. Erstellen wir eine boolesche Methode validPalindrome(String s), um zu überprüfen, ob String ein Palindrom ist. Java-Code ist hier:

public class PalindromeTest1 {

//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           if (s.charAt(i) != s.charAt(j)) {
               return false;
           }
       }
       return true;
   }

   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!"
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

In der Hauptmethode prüfen wir die palindromischen Zeichenfolgen „level“, „cool“, „Madam“ und „Jetzt, Sir, ein Krieg ist gewonnen!“. Wie Sie sehen können, sind das erste, dritte und vierte Palindrom, das zweite jedoch nicht. Was wird das Programm geben? Das erste ist also ein Palindrom, das zweite nicht. Was ist jedoch am dritten und vierten falsch? Warum ist das Ergebnis falsch ? Sie haben wahrscheinlich schon vermutet, dass einige Zeichen in dieser Zeichenfolge Großbuchstaben und andere Kleinbuchstaben sind und dass M und m für Java zwei verschiedene Zeichen sind. Lassen Sie uns das Programm verbessern, um diesen Unterschied zu berücksichtigen. Hier ist ein Programm zum Überprüfen, ob eine Zeichenfolge ein Palindrom ist, das Probleme mit Groß- und Kleinschreibung löst.

public class PalindromeTest2 {

   //lowercase and uppercase characters should be treated the same:
   public static boolean validPalindrome(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
               return false;
       }
       return true;
   }

   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
        String s4 = "Now, sir, a war is won!"
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

Diesmal ist das Ergebnis für uns vorhersehbarer: Nun ja ... nicht gerade vorhersehbar. Die Situation mit „Madam“ wird besser, aber was ist mit unserem langen und glücklichen Palindrom „Jetzt, Sir, ein Krieg ist gewonnen!“. Es ist ganz einfach, wenn Sie bedenken, dass alle Leerzeichen und Satzzeichen mit den Buchstaben für Java identisch sind. Daher müssen wir unseren Algorithmus erneut verbessern, um dieses Versehen zu korrigieren. Bringen wir unserem Programm bei, Leerzeichen und Satzzeichen zu ignorieren. Einfach ausgedrückt ignorieren wir alle nicht alphanumerischen Zeichen. Hier ist das verbesserte Palindromprogramm in Java.

public class PalindromeTest3 {

   //in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
   private static boolean isAlphanumeric(char c) {
       return Character.isAlphabetic(c) || Character.isDigit(c);
   }

   public static boolean validPalindromeIgnorePunctuation(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           // skip chars we should ignore
           while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
           while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
           // overskipped -> nothing left to validate
           if (i >= j) return true;

           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
               return false;
       }
       return true;
   }


   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!";
       boolean b1 = validPalindromeIgnorePunctuation(s1);
       boolean b2 = validPalindromeIgnorePunctuation(s2);
       boolean b3 = validPalindromeIgnorePunctuation(s3);
       boolean b4 = validPalindromeIgnorePunctuation(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

Zumindest ist das Ergebnis das, was wir davon erwartet haben: Wenn Sie gerade erst mit dem Programmieren beginnen, fällt es Ihnen vielleicht schwer zu verstehen, wie die String-Traversal- und Vergleichsalgorithmen funktionieren. Natürlich ist es besser, damit umzugehen, aber Sie können eine vereinfachte Version der Passage selbst durch das Zeichenarray schreiben, bei dem es sich tatsächlich um eine Zeichenfolge handelt. Sie können die Methode StringBuffer.reverse verwenden, um zu überprüfen, ob eine Zeichenfolge ein Palindrom ist. Machen wir die einfachste Version, ohne nach nicht-alphanumerischen Symbolen und Groß- und Kleinbuchstaben zu suchen.

public class PalindromeTest5 {

   public static boolean validPalindrome(String s) {

       StringBuffer buffer = new StringBuffer(s);
       buffer.reverse();
       String data = buffer.toString();

       if (s.equals(data)) {
           return true;
       }
       return false;
   }
   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!";
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }
}

Das Ergebnis ist das gleiche wie im allerersten Beispiel Wenn Sie möchten, können Sie dieses Programm so verbessern, wie wir es beim ersten Beispiel getan haben. Um das Gelernte zu vertiefen, empfehlen wir Ihnen, sich eine Videolektion aus unserem Java-Kurs anzusehen