Vérifiez si la chaîne est palindrome en Java

1. Utiliser des pointeurs pour vérifier si une chaîne est un palindrome en Java
2. Inverser la chaîne pour vérifier si une chaîne est un palindrome en Java
3. Utiliser la récursivité pour vérifier si une chaîne est un palindrome en Java
4. Conclusion

Si les caractères d’une chaîne de droite à gauche sont les mêmes que les caractères de la chaîne de gauche à droite, alors nous l’appelons un palindrome. Des chaînes comme ababa, radar et ppqpp en sont quelques exemples.

Ici, le premier caractère est le même que le dernier caractère ; le deuxième caractère est le même que l’avant-dernier caractère, etc. Dans cet article, nous allons nous intéresser aux différents programmes Java pour vérifier si une chaîne est un palindrome ou non.

Utiliser des pointeurs pour vérifier si une chaîne est un palindrome en Java

Une idée très simple pour vérifier si une chaîne est un palindrome ou non est d’utiliser deux pointeurs ; un point au début de la chaîne et l’autre point à la fin de la chaîne. Considérez le code suivant.

public class PalProgram {
  static boolean PalFunc(String s)

  {
    // Pointer i pointing to the start and j pointing to the end
    int i = 0, j = s.length() - 1;

    while (i < j) {
      // Check if there is any mis-matching pair
      if (s.charAt(i) != s.charAt(j))
        return false;

      // Update the pointers
      i++;
      j--;
    }

    // If no mismatch occurs
    return true;
  }

  public static void main(String[] args) {
    String s = "ava";
    s = s.toLowerCase();
    if (PalFunc(s))
      System.out.print("Yes, it is a palindrome.");

    else
      System.out.print("No, it is not a palindrome.");
  }
}

Production:

Yes, it is a palindrome.

Ici, à l’intérieur de la fonction PalFunc, le premier pointeur i pointera vers le début de la chaîne, et le deuxième pointeur j pointera vers la fin de la chaîne, dont nous devons vérifier s’il s’agit d’un palindrome ou pas.

Ensuite, nous allons exécuter une boucle jusqu’à i<j. A chaque étape, on vérifie si les caractères pointés par ces deux pointeurs, i et j, correspondent ou non.

De plus, nous incrémentons simultanément i et décrémentons j de un. Si les caractères ne correspondent à aucune étape, nous renvoyons false notifiant à l’utilisateur que la chaîne n’est pas un palindrome.

Nous utilisons la fonction toLowerCase() dans notre exemple. Le compilateur Java compare deux caractères en fonction de leurs valeurs ASCII.

Cela signifie que A == a évaluera false. Dans ce cas, la chaîne abA ne sera pas considérée comme un palindrome en Java, ce qui n’est pas le cas réel.

C’est pourquoi nous devons d’abord convertir la chaîne en majuscule ou en minuscule avant la comparaison dans la boucle for. C’est utile lorsqu’il s’agit de palindromes comme AVva, où les caractères mélangent majuscules et minuscules.

Inverser la chaîne pour vérifier si une chaîne est un palindrome en Java

Considérez que nous avons la chaîne aabcvbaa. Inversons d’abord la chaîne. La chaîne résultante sera aabvcbaa.

Le dernier caractère de la chaîne d’origine devient le premier caractère de la chaîne inversée. L’avant-dernier caractère de la chaîne d’origine devient le deuxième caractère de la chaîne inversée, et ainsi de suite.

Maintenant, nous pouvons comparer les deux chaînes caractère par caractère pour vérifier si la chaîne est un palindrome. Si une incompatibilité se produit, la chaîne n’est pas un palindrome, et nous pouvons retourner false, informant l’utilisateur que la chaîne n’est pas un palindrome.

Mais, s’il n’y a pas d’incompatibilité partout, nous pouvons retourner true, en disant que la chaîne est un palindrome. Dans ce cas, nous créons une nouvelle chaîne inversée au lieu d’utiliser deux pointeurs dans la même chaîne (voir la démonstration).

Parfois, nous ne sommes pas autorisés à utiliser les fonctions intégrées fournies en Java. Nous n’utiliserons donc pas la méthode reverse() des API Java.

Nous allons écrire notre fonction pour inverser la chaîne.

public class Solution {
  static boolean Sol(String s)

  {
    // reverse the string
    StringBuilder reversed_str = new StringBuilder();
    char[] newArray = s.toCharArray();
    for (int index = newArray.length - 1; index >= 0; index--) {
      reversed_str.append(newArray[index]);
    }

    // comparing the original string with the reversed string
    return (reversed_str.toString()).equals(s);
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes, this string is a palindrome.");

    else
      System.out.print("No, it isn't a palindrome.");
  }
}

Production:

Yes, this string is a palindrome.

Voyons rapidement ce qui se passe à l’intérieur de la fonction Sol. Nous changeons d’abord la chaîne en tableau, puis nous l’utilisons pour inverser la chaîne.

Ensuite, nous comparons la chaîne inversée avec la chaîne d’origine lettre par lettre.

1. Classe StringBuilder : La classe de chaînes en Java crée des chaînes immuables, c’est-à-dire des chaînes non modifiables. Ici, nous voulons créer une chaîne, reverse_str, qui est mutable pour y ajouter des caractères. La classe StringBuilder en Java nous aide à créer des chaînes mutables.
2. Méthode toCharArray : Puisque nous voulons comparer la chaîne originale et la chaîne inversée caractère par caractère, nous utilisons la méthode toCharArray pour convertir la chaîne en une série de caractères. On stocke le résultat dans le tableau newArray.
3. Méthode append() : après avoir changé la chaîne d’origine en un tableau de caractères, utilisez-la pour créer la chaîne inversée. Pour cela, nous parcourons le tableau de caractères à partir de la fin et continuons à ajouter les caractères dans la chaîne reverse_str en utilisant la méthode append().
4. Méthode toString() : nous le changeons à nouveau en chaîne en utilisant la méthode toString() après avoir créé la chaîne inversée. Nous faisons cela parce que nous pouvons comparer deux chaînes simplement en utilisant la méthode equals().

5. Méthode equals() : Enfin, nous comparons la chaîne originale s avec la chaîne inversée reversed_str. Pour ce faire, nous pouvons utiliser la méthode equals(), qui renvoie true si tous les caractères de la chaîne correspondent.

Nous pouvons facilement obtenir la même chose si nous utilisons la méthode reverse() des API Java - StringBuilder et StringBuffer, comme indiqué ci-dessous.

// Check if a string is a palindrome
// Java program

public class Solution {
  static boolean Sol(String s)

  { // Using the stringbuilder API
    StringBuilder newString = new StringBuilder(s);
    StringBuilder rev_str = newString.reverse();
    return (rev_str.toString()).equals(s);
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes, it is a palindrome.");

    else
      System.out.print("No, it is not a palindrome.");
  }
}

Production:

Yes, it is a palindrome.

Notez que lorsque nous utilisons l’API StringBuilder, nous n’avons pas besoin de créer des tableaux de caractères ou d’inverser la chaîne à l’aide d’une boucle for. Cette méthode est propre et simple.

Pour en savoir plus sur la classe StringBuilder, reportez-vous à cette documentation.

Nous pouvons également utiliser l’API StringBuilder, comme indiqué ci-dessous.

public class CheckPalindrome {
  static boolean Sol(String s)

  { // Using the stringbuffer API
    StringBuffer str = new StringBuffer(s);
    StringBuffer rev_str = str.reverse();
    return (rev_str.toString()).equals(s);
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes, it is a palindrome.");

    else
      System.out.print("No, it is not a palindrome.");
  }
}

Production:

Yes, it is a palindrome.

Vous vous demandez peut-être ce qui différencie les classes StringBuilder et StringBuffer car le code semble identique.

La classe StringBuffer n’autorise qu’un seul thread à appeler cette méthode à la fois. Il est synchronisé.

D’autre part, la méthode StringBuilder peut être appelée simultanément par plusieurs threads. Il n’est pas synchronisé.

Cependant, la classe StringBuilder est plus efficace que la classe StringBuffer. Pour en savoir plus sur la classe StringBuffer, reportez-vous à cette documentation.

Utiliser la récursivité pour vérifier si une chaîne est un palindrome en Java

On peut appeler récursivement la fonction Sol pour vérifier si une chaîne est un palindrome. L’idée de base est d’utiliser la récursivité pour itérer sur la chaîne.

public class Solution {
  static boolean Sol(String s)

  {
    s = s.toLowerCase();
    return RecursePal(s, 0, s.length() - 1);
  }

  static boolean RecursePal(String s, int f, int b) {
    if (f == b) {
      return true;
    }
    if ((s.charAt(f)) != (s.charAt(b))) {
      return false;
    }
    if (f < b + 1) {
      return RecursePal(s, f + 1, b - 1);
    }
    return true;
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes");

    else
      System.out.print("No");
  }
}

Production:

Yes

Ici, nous définissons une fonction, RecursePal. Nous passons la chaîne s, l’index du premier caractère comme f, et l’index du dernier caractère comme b comme arguments.

Ensuite, nous vérifions si le caractère en f est le même qu’en b. Si oui, on retourne true.

Sinon, on retourne false. Enfin, nous appelons à nouveau la fonction RecursePal pour répéter ce processus pour toute la chaîne.

Chaque fois que nous appelons récursivement cette fonction, nous incrémentons l’indice f et décrémentons l’indice b de un.

Conclusion

Dans ce tutoriel, nous avons vu les différentes manières en Java de vérifier si une chaîne est un Palindrome ou non.

Nous avons appris à utiliser deux pointeurs pour parcourir la chaîne dans les deux sens. Nous avons également vu comment vérifier si une chaîne est un palindrome en inversant la chaîne et en utilisant la récursivité en Java.