Compruebe si hay una cadena de palíndromo con una función recursiva en C++
- 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++](/img/Cpp/feature-image---palindrome-recursion-in-cpp.webp)
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
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 FacebookArtículo relacionado - C++ String
- Encuentre el primer carácter repetido en una cadena en C++
- Encuentre la subcadena común más larga en C++
- Poner en mayúscula la primera letra de una cadena en C++
- Comparación de cadenas y caracteres en C++
- Eliminar el último carácter de una cadena en C++
- Obtener el último carácter de una cadena en C++