Comment vérifier si une chaîne de caractères est un palindrome en Java

Introduction

Dans ce laboratoire, vous apprendrez à vérifier si une chaîne de caractères est un palindrome en Java. Nous explorerons différentes approches, en commençant par la méthode fondamentale consistant à inverser une chaîne de caractères et à la comparer avec l'originale.

En nous appuyant sur cela, vous apprendrez ensuite une technique plus efficace utilisant l'approche des deux pointeurs (two-pointer approach). Enfin, nous améliorerons notre vérification de palindrome pour ignorer la casse et les caractères non alphabétiques, rendant ainsi la vérification plus robuste.

Skills Graph

Inverser une chaîne de caractères et comparer

Dans cette étape, nous allons commencer par créer un simple programme Java pour inverser une chaîne de caractères, puis la comparer avec la chaîne originale. Ceci est une étape fondamentale pour comprendre la manipulation de chaînes de caractères en Java et servira de base pour vérifier si une chaîne de caractères est un palindrome.

Tout d'abord, créons un nouveau fichier Java. Dans l'explorateur de fichiers situé à gauche de l'IDE Web, cliquez avec le bouton droit dans le répertoire ~/project, sélectionnez "Nouveau fichier" et nommez-le StringReverse.java.

Maintenant, ouvrez le fichier StringReverse.java dans l'éditeur et ajoutez le code suivant :

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.");
        }
    }
}

Décortiquons ce code :

• String originalString = "hello"; : Nous déclarons une variable de type String nommée originalString et lui assignons la valeur "hello".
• String reversedString = ""; : Nous déclarons une variable de type String vide nommée reversedString. Nous allons construire la chaîne inversée ici.
• for (int i = originalString.length() - 1; i >= 0; i--) : Il s'agit d'une boucle for qui commence par le dernier caractère de la originalString (index length() - 1) et descend jusqu'au premier caractère (index 0).
• reversedString += originalString.charAt(i); : À l'intérieur de la boucle, originalString.charAt(i) récupère le caractère à l'index i actuel. Nous ajoutons ensuite ce caractère à la reversedString.
• System.out.println(...) : Ces lignes affichent les chaînes originales et inversées dans la console.
• if (originalString.equals(reversedString)) : Cette instruction if compare la originalString et la reversedString à l'aide de la méthode equals(). En Java, vous devez utiliser equals() pour comparer le contenu des chaînes de caractères, pas l'opérateur ==.
• Les blocs if et else affichent différents messages en fonction de si les chaînes sont identiques.

Enregistrez le fichier StringReverse.java (Ctrl+S ou Cmd+S).

Maintenant, ouvrez le terminal en bas de l'IDE Web. Assurez-vous d'être dans le répertoire ~/project. Sinon, tapez cd ~/project et appuyez sur Entrée.

Compilez le code Java en utilisant la commande javac :

javac StringReverse.java

S'il n'y a pas d'erreurs, un fichier StringReverse.class sera créé dans le répertoire ~/project.

Enfin, exécutez le programme Java compilé en utilisant la commande java :

java StringReverse

Vous devriez voir une sortie similaire à ceci :

Original string: hello
Reversed string: olleh
The string is NOT the same forwards and backwards.

Dans ce cas, "hello" n'est pas le même dans les deux sens, donc le programme l'identifie correctement.

Utiliser l'approche des deux pointeurs (two-pointer approach) pour vérifier les palindromes

Dans l'étape précédente, nous avons inversé toute la chaîne de caractères pour vérifier si elle était un palindrome. Bien que cette méthode fonctionne, elle nécessite de créer une nouvelle chaîne de caractères, ce qui peut être inefficace pour des chaînes très longues. Une approche plus efficace consiste à utiliser la technique des deux pointeurs (two-pointer technique).

La technique des deux pointeurs consiste à utiliser deux pointeurs (variables qui contiennent des positions d'index) qui commencent aux extrémités opposées de la chaîne de caractères et se déplacent vers le centre. Nous comparons les caractères aux positions de ces pointeurs. Si les caractères sont toujours identiques à mesure que les pointeurs se déplacent vers l'intérieur, la chaîne de caractères est un palindrome. Si nous trouvons une différence, ce n'est pas un palindrome.

Créons un nouveau programme Java pour implémenter cela. Dans l'explorateur de fichiers à gauche, créez un nouveau fichier nommé PalindromeChecker.java dans le répertoire ~/project.

Ouvrez PalindromeChecker.java et ajoutez le code suivant :

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

Voici ce qui se passe dans le nouveau code :

• Nous avons créé une méthode distincte appelée checkPalindrome qui prend une String en entrée et renvoie un boolean (true si c'est un palindrome, false sinon). Cela rend notre code plus organisé et réutilisable.
• À l'intérieur de checkPalindrome, nous initialisons left à 0 (l'index du premier caractère) et right à str.length() - 1 (l'index du dernier caractère).
• La boucle while (left < right) continue tant que le pointeur de gauche est à gauche du pointeur de droite.
• if (str.charAt(left) != str.charAt(right)) compare les caractères aux positions left et right actuelles. Si ils sont différents, nous savons immédiatement que ce n'est pas un palindrome et nous renvoyons false.
• Si les caractères correspondent, nous déplaçons les pointeurs vers l'intérieur : left++ incrémente le pointeur de gauche, et right-- décrémente le pointeur de droite.
• Si la boucle se termine sans renvoyer false, cela signifie que tous les caractères comparés correspondent, donc la chaîne de caractères est un palindrome, et nous renvoyons true.
• Dans la méthode main, nous appelons checkPalindrome avec différentes chaînes de test et affichons les résultats.

Enregistrez le fichier PalindromeChecker.java.

Maintenant, compilez et exécutez le programme dans le terminal :

javac PalindromeChecker.java
java PalindromeChecker

Vous devriez voir la sortie suivante :

"madam" is a palindrome.
"racecar" is a palindrome.
"hello" is not a palindrome.

Cela démontre comment l'approche des deux pointeurs vérifie efficacement les palindromes sans inverser toute la chaîne de caractères.

Ignorer la casse et les caractères non-alphabétiques dans les palindromes

Dans l'étape précédente, notre vérificateur de palindromes fonctionnait pour des chaînes simples comme "madam" et "racecar". Cependant, les palindromes du monde réel ignorent souvent la casse et la ponctuation. Par exemple, "A man, a plan, a canal: Panama" est considéré comme un palindrome.

Dans cette étape, nous allons améliorer notre PalindromeChecker pour gérer ces cas en ignorant les caractères non-alphabétiques et en traitant les lettres majuscules et minuscules de la même manière.

Ouvrez le fichier PalindromeChecker.java dans l'éditeur de l'IDE Web. Nous allons modifier la méthode checkPalindrome.

Remplacez la méthode checkPalindrome existante par la version mise à jour suivante :

    // 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;
    }

Voici les modifications que nous avons apportées :

• Nous avons ajouté deux boucles while à l'intérieur de la boucle principale while (left < right).
• La première boucle while interne (while (left < right && !Character.isLetter(str.charAt(left)))) déplace le pointeur left vers l'avant tant qu'il est toujours à gauche du pointeur right et que le caractère au pointeur left n'est pas une lettre (!Character.isLetter(...)).
• La deuxième boucle while interne (while (left < right && !Character.isLetter(str.charAt(right)))) déplace le pointeur right vers l'arrière tant qu'il est toujours à gauche du pointeur right et que le caractère au pointeur right n'est pas une lettre.
• La comparaison if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) inclut maintenant deux vérifications importantes :
  • left < right : Cela garantit que nous ne comparons les caractères que si les pointeurs ne se sont pas croisés après avoir sauté les caractères non-alphabétiques.
  • Character.toLowerCase(...) : Cela convertit les deux caractères en minuscules avant de les comparer, ignorant ainsi la casse.
• Si les caractères (après conversion en minuscules) ne correspondent pas, nous renvoyons false.
• Si ils correspondent, nous déplaçons les deux pointeurs vers l'intérieur (left++, right--) pour vérifier la paire de caractères suivante.

Maintenant, modifions la méthode main pour tester avec une chaîne qui inclut des espaces, de la ponctuation et une casse mixte. Remplacez les cas de test existants dans la méthode main par ceci :

    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.");
        }
    }

Enregistrez le fichier PalindromeChecker.java.

Compilez et exécutez le programme mis à jour dans le terminal :

javac PalindromeChecker.java
java PalindromeChecker

Vous devriez maintenant voir la sortie suivante, identifiant correctement les palindromes même avec des caractères non-alphabétiques et une casse mixte :

"A man, a plan, a canal: Panama" is a palindrome.
"No 'x' in Nixon" is a palindrome.
"hello world" is not a palindrome.

Vous avez réussi à améliorer votre vérificateur de palindromes pour gérer des chaînes plus complexes !

Résumé

Dans ce laboratoire (lab), nous avons appris à vérifier si une chaîne de caractères est un palindrome en Java. Nous avons commencé par implémenter une méthode pour inverser une chaîne de caractères et la comparer à la chaîne originale pour déterminer si c'est un palindrome. Cela a impliqué la création d'un fichier Java, l'écriture de code pour parcourir la chaîne de caractères en sens inverse et l'utilisation de la méthode equals() pour la comparaison.

Nous avons ensuite exploré l'approche des deux pointeurs (two-pointer approach), une méthode plus efficace pour vérifier les palindromes qui évite de créer une nouvelle chaîne de caractères inversée. Enfin, nous avons amélioré notre vérification de palindrome pour ignorer la casse et les caractères non-alphabétiques, rendant la vérification plus robuste pour les scénarios du monde réel.