Además de ser el Día de la Marmota, el día de hoy nos presenta una fecha especial, un palíndromo: 02022020. Un palíndromo es un texto que se lee de igual forma en un sentido que en otro: ANA, amor a Roma (salvando la mayúscula), oso, ojo…
Hoy dedicaremos un artículo básico sobre cómo comprobar si un texto es palíndromo o no. Es un buen ejercicio cuando se comienza a programar y he querido dedicar unas líneas al mismo con algunas soluciones. En términos generales, todas implican comparar el primer caracter con el último, el segundo con el penúltimo y así hasta llegar a la mitad o encontrar uno diferente.
Por simplicidad, diferenciaremos mayúsculas de minúsculas así como letras acentuadas; es decir, Ojo no sería palíndromo pero ojo sí. Solventarlo es sencillo pero creo que añadiría complejidad innecesaria a los ejemplos.
Cadena terminada en null (estilo C)
Esta solución presupone que conocemos la longitud de la cadena (de no saberla se puede calcular usando strlen)
bool is_palindrome(const char* str, size_t len)
{
if (len == 0) return true;
for (size_t ii = 0, jj = len - 1; ii < jj; ++ii, --jj) {
if (str[ii] != str[jj]) return false;
}
return true;
}
std::string (o en general cualquier contenedor secuencial de caracteres)
Si bien se pudiese usar la misma solución de antes (por ejemplo is_palindrome(str.c_str(), str.size()), he preferido mostrar el uso del algoritmo de la STL std::equal y el iterador en reversa:
template<class T>
bool is_palindrome(const T& str)
{
using namespace std;
return equal(begin(str), end(str), rbegin(str));
}
Hay que tener cuidado con el uso del std::rbegin en literales de texto, ya que el último elemento de la cadena es el caracter nulo. Así, "oso" es realmente un const char[4] (3 letras más el nulo). La solución viene por especializar la función para este caso y omitir ese último caracter:
template<size_t N>
bool is_palindrome(const char (&str)[N])
{
return is_palindrome(str, N - 1);
}
Código completo
El ejemplo completo puede encontrarse en Coliru y en Github.
Mejoras
El código presentado es básico, dejamos abiertas las siguientes posibles mejoras:
- No diferenciar entre mayúsculas y minúsculas
- Ignorar espacios
