Compruebe si hay una cadena de palíndromo con una función recursiva en C++

Jinku Hu 12 octubre 2023

C++ C++ String

Utilice la función recursiva para comprobar si hay una cadena de palíndromo
Utilice el algoritmo std::equal Comprobación de una cadena Palindrome

Compruebe si hay una cadena de palíndromo con una función recursiva en C++

Este artículo explicará varios métodos para verificar una cadena palíndromo con una función recursiva en C++.

Utilice la función recursiva para comprobar si hay una cadena de palíndromo

Una función recursiva es la que se llama a sí misma desde el cuerpo de la función. Un método recursivo no es la forma óptima de implementar un algoritmo de verificación palíndromo. La función isPalindrome toma tres argumentos y devuelve un valor booleano para indicar si la cadena pasada es un palíndromo. El segundo y tercer argumento se utilizan para almacenar las posiciones inicial y final de la secuencia de cadenas. Como primera condición, evaluamos si la longitud de la cadena es 1, y si es así, la función regresa inmediatamente con un valor afirmativo. A continuación, se comparan el primer y el último carácter y, si no son iguales, la función devuelve false. De lo contrario, la ejecución continúa verificando si la cadena contiene más caracteres en el medio de las posiciones actuales st y en. Si la condición se evalúa como verdadera, entonces la llamada recursiva se realiza con posiciones cambiadas y el mismo valor de cadena. Por otro lado, la condición falsa obliga a la función a devolver 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;
}

Producción :

s1 is a palindrome
s2 is not a palindrome

Observe que la solución anterior no puede identificar los palíndromos con letras y espacios mixtos como el objeto s2. Por lo tanto, debemos convertir la cadena a las mismas letras mayúsculas y minúsculas y eliminar los espacios para encontrar todos los palíndromos válidos correctamente. El algoritmo std::trasform y el idioma erase-remove se utilizan para analizar la cadena a la forma compatible para la función 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;
}

Producción :

s2 is a palindrome

Utilice el algoritmo `std::equal` Comprobación de una cadena Palindrome

std::equal es parte de la biblioteca de plantillas estándar de C++ y se puede utilizar para comparar rangos. Por lo tanto, dado que la clase string tiene la interfaz de iterador, podemos especificar su rango con las funciones begin y rbegin. Sin embargo, tenga en cuenta que la siguiente versión de sobrecarga std::equal toma tres argumentos, los dos primeros de los cuales especifican el primer rango, mientras que el tercer argumento denota el comienzo del segundo rango.

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

Producción :

s2 is a palindrome

Autor: 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

Utilice la función recursiva para comprobar si hay una cadena de palíndromo

Utilice el algoritmo std::equal Comprobación de una cadena Palindrome

Artículo relacionado - C++ String

Utilice el algoritmo `std::equal` Comprobación de una cadena Palindrome