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 !
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 ?
est-ce que le niveau est un palindrome ? vrai
est cool un palindrome? faux
Madame est-elle un palindrome ? faux
est Maintenant, monsieur, une guerre est gagnée! un palindrome ? FAUX
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 :
est-ce que le niveau est un palindrome ? vrai
est cool un palindrome? faux
Madame est-elle un palindrome ? vrai
est Maintenant, monsieur, une guerre est gagnée! un palindrome ? FAUX
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 :
est-ce que le niveau est un palindrome ? vrai
est cool un palindrome? faux
Madame est-elle un palindrome ? vrai
est Maintenant, monsieur, une guerre est gagnée! un palindrome ? vrai
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
est-ce que le niveau est un palindrome ? vrai
est cool un palindrome? faux
Madame est-elle un palindrome ? faux
est Maintenant, monsieur, une guerre est gagnée! un palindrome ? FAUX
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
GO TO FULL VERSION