Programme Java pour vérifier qu'une chaîne est un palindrome

Certains problèmes de programmation ont le statut de problèmes classiques. Généralement, ces tâches sont liées aux mathématiques et ils aiment beaucoup demander aux étudiants des spécialités en informatique, ainsi qu'aux demandeurs d'emploi lors d'entretiens. Ils sont bons parce qu'ils aident assez bien à mettre en place votre pensée à la manière d'un programmeur, ainsi qu'à l'entraîner. L'un de ces problèmes est de vérifier si une chaîne est un palindrome, et nous allons l'examiner dans cet article.

Qu'est-ce qu'un palindrome et pourquoi pouvoir les chercher

Un palindrome est un nombre, une combinaison de lettres, un mot ou un texte qui se lit de la même manière dans les deux sens. Pour résumer, un palindrome peut être appelé n'importe quel ensemble de caractères symétriques par rapport à son milieu. Le mot vient des racines grecques qui dérivent littéralement de « courir en arrière » (palin signifie « encore, en arrière » et dromos, « courir »). Palindrome en Java signifie la même chose qu'au sens général. Exemples de palindromes :

• 1881
• aaqquqqaa
• populaire
• Midi
• niveau
• Rotateur
• Ma salle de gym
• Madame je suis Adam
• Maintenant, monsieur, une guerre est gagnée !

1881 est un nombre palindrome et les autres sont des cordes palindromes. Dans cet article, nous examinerons les palindromes représentés sous forme de chaînes, mais certains algorithmes sont tout à fait applicables à d'autres types de palindromes en Java. Pourquoi pourriez-vous chercher des palindromes? En fait, nous n'avons pas souvent à chercher des palindromes dans la vie de tous les jours. C'est une sorte de tâche très spécifique. Si nous rappelons les algorithmes de chaîne, plus souvent dans la pratique, les programmeurs peuvent trouver la recherche d'une sous-chaîne dans une chaîne, et non la recherche de palindromes ou de leur nombre. Cependant, les problèmes liés aux palindromes ont des applications importantes. Le premier est la programmation olympique. Il pourrait y avoir des tâches pour identifier les palindromes. La deuxième application pertinente pour les programmeurs novices est l'entretien. Lors d'un entretien technique, on peut très bien vous demander d'écrire rapidement un programme pour vérifier si une chaîne est palindrome, peut-être même sur une feuille de papier. Eh bien, en science, l'application la plus pratique pour trouver des palindromes est les algorithmes biologiques. Selon Wikipedia, la palindromicité des composés biologiques joue un rôle important dans les propriétés de divers composés biologiques.

Exemple de code d'algorithme Palindrome

Réfléchissons. Une chaîne est une séquence de caractères, pourrait-on dire, un tableau de caractères. Il serait plus logique de suivre cette séquence des deux côtés vers le milieu et de comparer les caractères extrêmes. Si jusqu'à ce que nous atteignions le milieu, tous nos caractères correspondent, alors nous avons un palindrome. Créons une méthode booléenne validPalindrome(String s) pour vérifier si String est palindrome. Le code Java est ici :

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);


   }

}

Dans la méthode principale, nous vérifions les chaînes palindromiques "niveau", "cool", "Madame" et "Maintenant, monsieur, une guerre est gagnée !". Comme vous pouvez le voir, les premier, troisième et quatrième sont des palindromes, mais le second ne l'est pas. Que va donner le programme ? Ainsi, le premier est un palindrome, le second ne l'est pas. Cependant, qu'est-ce qui ne va pas avec le troisième et le quatrième? Pourquoi le résultat est- il faux ? Vous avez probablement déjà deviné que le fait est que certains caractères de cette chaîne sont en majuscules et d'autres en minuscules, et pour Java M et m sont deux caractères différents. Améliorons le programme pour tenir compte de cette différence. Voici un programme pour vérifier si une chaîne est un palindrome qui résout les problèmes de majuscules et minuscules.

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);


   }

}

Cette fois, le résultat est plus prévisible pour nous : Eh bien… pas exactement prévisible. La situation avec "Madame" s'améliore, mais qu'en est-il de notre long et heureux palindrome "Maintenant, monsieur, une guerre est gagnée!". C'est assez facile, si vous vous souvenez que tous les espaces et symboles de ponctuation sont les mêmes que les lettres pour Java. Nous devons donc encore améliorer notre algorithme pour corriger cet oubli. Apprenons à notre programme à ignorer les espaces et la ponctuation. En termes simples, nous ignorons tous les caractères non alphanumériques. Voici le programme palindrome amélioré en 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);


   }

}

Au moins le résultat est ce que nous en attendions : Peut-être, si vous commencez tout juste à programmer, il vous est difficile de comprendre comment fonctionnent les algorithmes de parcours et de comparaison de chaînes. Bien sûr, il vaut mieux gérer cela, mais vous pouvez écrire une version simplifiée du passage même à travers le tableau de caractères, qui est en fait une chaîne. Vous pouvez utiliser la méthode StringBuffer.reverse pour vérifier si une chaîne est un palindrome. Faisons la version la plus simple sans vérifier les symboles non alphanumériques et les majuscules et minuscules.

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);


   }
}

Le résultat est le même que dans le tout premier exemple Si vous le souhaitez, vous pouvez améliorer ce programme comme nous l'avons fait avec le premier exemple. Pour renforcer ce que vous avez appris, nous vous suggérons de regarder une leçon vidéo de notre cours Java