Rechercher une chaîne Palindrome avec une fonction récursive en C++

Jinku Hu 12 octobre 2023

C++ C++ String

Utiliser la fonction récursive pour rechercher une chaîne Palindrome
Utiliser l’algorithme std::equal pour vérifier la présence d’une chaîne palindrome

Rechercher une chaîne Palindrome avec une fonction récursive en C++

Cet article explique plusieurs méthodes de vérification d’une chaîne palindrome avec une fonction récursive en C++.

Utiliser la fonction récursive pour rechercher une chaîne Palindrome

Une fonction récursive est celle qui s’appelle elle-même à partir du corps de la fonction. Une méthode récursive n’est pas la manière optimale d’implémenter un algorithme de vérification de palindrome. La fonction isPalindrome prend trois arguments et renvoie une valeur booléenne pour indiquer si la chaîne passée est un palindrome. Les deuxième et troisième arguments sont utilisés pour stocker les positions de début et de fin de la séquence de chaînes. Comme première condition, nous évaluons si la longueur de la chaîne est 1, et si c’est le cas, la fonction retourne immédiatement avec une valeur affirmative. Ensuite, le premier et le dernier caractère sont comparés, et s’ils ne sont pas égaux, la fonction renvoie false. Sinon, l’exécution continue de vérifier si la chaîne contient plus de caractères au milieu des positions actuelles st et en. Si la condition évalue true, l’appel récursif est effectué avec des positions décalées et la même valeur de chaîne. Par contre, la condition fausse oblige la fonction à retourner true.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

bool isPalindrome(const string &s, size_t st, size_t en) {
  if (s.length() == 1) return true;

  if (s[st] != s[en - 1]) return false;

  if (st < en + 1) return isPalindrome(s, st + 1, en - 1);

  return true;
}

int main() {
  string s1 = "radar";
  string s2 = "Was it a cat I saw";

  isPalindrome(s1, 0, s1.length()) ? cout << "s1 is a palindrome" << endl
                                   : cout << "s1 is not a palindrome" << endl;

  isPalindrome(s2, 0, s2.length()) ? cout << "s2 is a palindrome" << endl
                                   : cout << "s2 is not a palindrome" << endl;

  return EXIT_SUCCESS;
}

Production:

s1 is a palindrome
s2 is not a palindrome

Notez que la solution précédente ne peut pas identifier les palindromes avec des lettres à casse mixte et des espaces tels que l’objet s2. Nous devons donc convertir la chaîne en lettres majuscules et supprimer tous les espaces pour trouver correctement tous les palindromes valides. L’algorithme std::trasform et l’idiome effacer-supprimer sont utilisés pour analyser la chaîne sous la forme compatible pour la fonction isPalindrome.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

bool isPalindrome(const string &s, size_t st, size_t en) {
  if (s.length() == 1) return true;

  if (s[st] != s[en - 1]) return false;

  if (st < en + 1) return isPalindrome(s, st + 1, en - 1);

  return true;
}

int main() {
  string s2 = "Was it a cat I saw";

  transform(s2.begin(), s2.end(), s2.begin(),
            [](unsigned char c) { return tolower(c); });
  s2.erase(remove(s2.begin(), s2.end(), ' '), s2.end());

  isPalindrome(s2, 0, s2.length()) ? cout << "s2 is a palindrome" << endl
                                   : cout << "s2 is not a palindrome" << endl;

  return EXIT_SUCCESS;
}

Production:

s2 is a palindrome

Utiliser l’algorithme `std::equal` pour vérifier la présence d’une chaîne palindrome

std::equal fait partie de la bibliothèque de modèles standard C++ et peut être utilisé pour comparer des plages. Ainsi, puisque la classe string a l’interface d’itérateur, nous pouvons spécifier sa plage avec les fonctions begin et rbegin. Notez cependant que la version de surcharge std::equal suivante prend trois arguments, dont les deux premiers spécifient la première plage, tandis que le troisième argument désigne le début de la deuxième plage.

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::equal;
using std::remove;
using std::string;

bool checkPalindrome(string& s) {
  string tmp = s;
  transform(tmp.begin(), tmp.end(), tmp.begin(),
            [](unsigned char c) { return tolower(c); });
  tmp.erase(remove(tmp.begin(), tmp.end(), ' '), tmp.end());

  if (equal(tmp.begin(), tmp.begin() + tmp.size() / 2, tmp.rbegin())) {
    return true;
  } else {
    return false;
  }
}

int main() {
  string s1 = "radar";
  string s2 = "Was it a cat I saw";

  checkPalindrome(s2) ? cout << "s2 is a palindrome" << endl
                      : cout << "s2 is not a palindrome" << endl;

  return EXIT_SUCCESS;
}

Production:

s2 is a palindrome

Auteur: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Utiliser la fonction récursive pour rechercher une chaîne Palindrome

Utiliser l’algorithme std::equal pour vérifier la présence d’une chaîne palindrome

Article connexe - C++ String

Utiliser l’algorithme `std::equal` pour vérifier la présence d’une chaîne palindrome