Cómo verificar si una cadena es un palíndromo en Java

Introducción

En este laboratorio, aprenderás cómo verificar si una cadena (string) es un palíndromo en Java. Exploraremos diferentes enfoques, comenzando con el método fundamental de invertir una cadena y compararla con la original.

A partir de esto, luego aprenderás una técnica más eficiente utilizando el enfoque de dos punteros (two-pointer approach). Finalmente, mejoraremos nuestra comprobación de palíndromos para ignorar mayúsculas y minúsculas y caracteres no alfabéticos, lo que hará la comprobación más robusta.

Skills Graph

Invertir y comparar una cadena (string)

En este paso, comenzaremos creando un sencillo programa en Java para invertir una cadena y luego compararla con la cadena original. Este es un paso fundamental para comprender la manipulación de cadenas en Java y servirá como base para verificar si una cadena es un palíndromo.

Primero, creemos un nuevo archivo Java. En el Explorador de archivos en el lado izquierdo del WebIDE, haz clic derecho en el directorio ~/project, selecciona "Nuevo archivo" y asígnalo el nombre StringReverse.java.

Ahora, abre el archivo StringReverse.java en el editor y agrega el siguiente código:

public class StringReverse {

    public static void main(String[] args) {
        String originalString = "hello";
        String reversedString = "";

        // Loop through the original string from end to beginning
        for (int i = originalString.length() - 1; i >= 0; i--) {
            // Append each character to the reversedString
            reversedString += originalString.charAt(i);
        }

        System.out.println("Original string: " + originalString);
        System.out.println("Reversed string: " + reversedString);

        // Compare the original and reversed strings
        if (originalString.equals(reversedString)) {
            System.out.println("The string is the same forwards and backwards.");
        } else {
            System.out.println("The string is NOT the same forwards and backwards.");
        }
    }
}

Desglosemos este código:

• String originalString = "hello";: Declaramos una variable de tipo String llamada originalString y le asignamos el valor "hello".
• String reversedString = "";: Declaramos una variable de tipo String vacía llamada reversedString. Aquí construiremos la cadena invertida.
• for (int i = originalString.length() - 1; i >= 0; i--): Este es un bucle for que comienza desde el último carácter de la originalString (índice length() - 1) y va hacia atrás hasta el primer carácter (índice 0).
• reversedString += originalString.charAt(i);: Dentro del bucle, originalString.charAt(i) obtiene el carácter en el índice actual i. Luego, agregamos este carácter a la reversedString.
• System.out.println(...): Estas líneas imprimen la cadena original y la cadena invertida en la consola.
• if (originalString.equals(reversedString)): Esta instrucción if compara la originalString y la reversedString utilizando el método equals(). En Java, se debe usar equals() para comparar el contenido de las cadenas, no el operador ==.
• Los bloques if y else imprimen mensajes diferentes según si las cadenas son iguales o no.

Guarda el archivo StringReverse.java (Ctrl+S o Cmd+S).

Ahora, abre la Terminal en la parte inferior del WebIDE. Asegúrate de estar en el directorio ~/project. Si no lo estás, escribe cd ~/project y presiona Enter.

Compila el código Java utilizando el comando javac:

javac StringReverse.java

Si no hay errores, se creará un archivo StringReverse.class en el directorio ~/project.

Finalmente, ejecuta el programa Java compilado utilizando el comando java:

java StringReverse

Deberías ver una salida similar a esta:

Original string: hello
Reversed string: olleh
The string is NOT the same forwards and backwards.

En este caso, "hello" no es igual de adelante hacia atrás, por lo que el programa lo identifica correctamente.

Utilizar el enfoque de dos punteros (two-pointer approach) para palíndromos

En el paso anterior, invertimos toda la cadena (string) para verificar si era un palíndromo. Aunque esto funciona, requiere crear una nueva cadena, lo cual puede ser ineficiente para cadenas muy largas. Un enfoque más eficiente es utilizar la técnica de dos punteros (two-pointer technique).

La técnica de dos punteros consiste en utilizar dos punteros (variables que almacenan posiciones de índice) que comienzan en extremos opuestos de la cadena y se mueven hacia el centro. Comparamos los caracteres en estos punteros. Si siempre son iguales a medida que los punteros se mueven hacia adentro, la cadena es un palíndromo. Si encontramos alguna discrepancia, no es un palíndromo.

Creemos un nuevo programa Java para implementar esto. En el Explorador de archivos a la izquierda, crea un nuevo archivo llamado PalindromeChecker.java en el directorio ~/project.

Abre PalindromeChecker.java y agrega el siguiente código:

public class PalindromeChecker {

    public static void main(String[] args) {
        String testString = "madam"; // Let's test with a palindrome
        boolean isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "racecar"; // Another palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "hello"; // Not a palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }
    }

    // Method to check if a string is a palindrome using two pointers
    public static boolean checkPalindrome(String str) {
        // Initialize two pointers
        int left = 0; // Pointer starting from the beginning
        int right = str.length() - 1; // Pointer starting from the end

        // Loop while the left pointer is less than the right pointer
        while (left < right) {
            // Compare characters at the left and right pointers
            if (str.charAt(left) != str.charAt(right)) {
                // If characters don't match, it's not a palindrome
                return false;
            }
            // Move the pointers inwards
            left++;
            right--;
        }

        // If the loop completes without finding any mismatch, it's a palindrome
        return true;
    }
}

Esto es lo que sucede en el nuevo código:

• Hemos creado un método separado llamado checkPalindrome que toma una String como entrada y devuelve un boolean (true si es un palíndromo, false en caso contrario). Esto hace que nuestro código sea más organizado y reutilizable.
• Dentro de checkPalindrome, inicializamos left en 0 (el índice del primer carácter) y right en str.length() - 1 (el índice del último carácter).
• El bucle while (left < right) continúa mientras el puntero izquierdo esté a la izquierda del puntero derecho.
• if (str.charAt(left) != str.charAt(right)) compara los caracteres en las posiciones left y right actuales. Si son diferentes, inmediatamente sabemos que no es un palíndromo y devolvemos false.
• Si los caracteres coinciden, movemos los punteros hacia adentro: left++ incrementa el puntero izquierdo y right-- decrementa el puntero derecho.
• Si el bucle finaliza sin devolver false, significa que todos los caracteres comparados coincidieron, por lo que la cadena es un palíndromo y devolvemos true.
• En el método main, llamamos a checkPalindrome con diferentes cadenas de prueba e imprimimos los resultados.

Guarda el archivo PalindromeChecker.java.

Ahora, compila y ejecuta el programa en la Terminal:

javac PalindromeChecker.java
java PalindromeChecker

Deberías ver la siguiente salida:

"madam" is a palindrome.
"racecar" is a palindrome.
"hello" is not a palindrome.

Esto demuestra cómo el enfoque de dos punteros verifica de manera eficiente los palíndromos sin invertir toda la cadena.

Ignorar mayúsculas/minúsculas y caracteres no alfabéticos en palíndromos

En el paso anterior, nuestro verificador de palíndromos funcionaba para cadenas (strings) simples como "madam" y "racecar". Sin embargo, los palíndromos del mundo real a menudo ignoran la capitalización y la puntuación. Por ejemplo, "A man, a plan, a canal: Panama" se considera un palíndromo.

En este paso, mejoraremos nuestro PalindromeChecker para manejar estos casos ignorando los caracteres no alfabéticos y tratando las letras mayúsculas y minúsculas por igual.

Abre el archivo PalindromeChecker.java en el editor del WebIDE. Modificaremos el método checkPalindrome.

Reemplaza el método checkPalindrome existente con la siguiente versión actualizada:

    // Method to check if a string is a palindrome using two pointers,
    // ignoring case and non-letter characters
    public static boolean checkPalindrome(String str) {
        // Initialize two pointers
        int left = 0; // Pointer starting from the beginning
        int right = str.length() - 1; // Pointer starting from the end

        // Loop while the left pointer is less than the right pointer
        while (left < right) {
            // Move left pointer past non-letter characters
            while (left < right && !Character.isLetter(str.charAt(left))) {
                left++;
            }

            // Move right pointer past non-letter characters
            while (left < right && !Character.isLetter(str.charAt(right))) {
                right--;
            }

            // If left and right pointers haven't crossed and characters don't match (ignoring case)
            if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) {
                // If characters don't match, it's not a palindrome
                return false;
            }

            // Move the pointers inwards
            left++;
            right--;
        }

        // If the loop completes without finding any mismatch, it's a palindrome
        return true;
    }

Estos son los cambios que hicimos:

• Agregamos dos bucles while dentro del bucle principal while (left < right).
• El primer bucle while interno (while (left < right && !Character.isLetter(str.charAt(left)))) mueve el puntero left hacia adelante siempre que esté a la izquierda del puntero right y el carácter en el puntero left no sea una letra (!Character.isLetter(...)).
• El segundo bucle while interno (while (left < right && !Character.isLetter(str.charAt(right)))) mueve el puntero right hacia atrás siempre que esté a la izquierda del puntero right y el carácter en el puntero right no sea una letra.
• La comparación if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) ahora incluye dos comprobaciones importantes:
  • left < right: Esto asegura que solo comparemos caracteres si los punteros no se han cruzado después de omitir los caracteres no alfabéticos.
  • Character.toLowerCase(...): Esto convierte ambos caracteres a minúsculas antes de compararlos, ignorando efectivamente las mayúsculas y minúsculas.
• Si los caracteres (después de convertirlos a minúsculas) no coinciden, devolvemos false.
• Si coinciden, movemos ambos punteros hacia adentro (left++, right--) para comprobar el siguiente par de caracteres.

Ahora, modifiquemos el método main para probar con una cadena que incluya espacios, puntuación y mayúsculas y minúsculas mezcladas. Reemplaza los casos de prueba existentes en el método main con esto:

    public static void main(String[] args) {
        String testString = "A man, a plan, a canal: Panama"; // A classic palindrome
        boolean isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "No 'x' in Nixon"; // Another palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }

        testString = "hello world"; // Not a palindrome
        isPalindrome = checkPalindrome(testString);

        if (isPalindrome) {
            System.out.println("\"" + testString + "\" is a palindrome.");
        } else {
            System.out.println("\"" + testString + "\" is not a palindrome.");
        }
    }

Guarda el archivo PalindromeChecker.java.

Compila y ejecuta el programa actualizado en la Terminal:

javac PalindromeChecker.java
java PalindromeChecker

Ahora deberías ver la siguiente salida, identificando correctamente los palíndromos incluso con caracteres no alfabéticos y mayúsculas y minúsculas mezcladas:

"A man, a plan, a canal: Panama" is a palindrome.
"No 'x' in Nixon" is a palindrome.
"hello world" is not a palindrome.

¡Has mejorado con éxito tu verificador de palíndromos para manejar cadenas más complejas!

Resumen

En este laboratorio (lab), aprendimos cómo verificar si una cadena (string) es un palíndromo en Java. Comenzamos implementando un método para invertir una cadena y comparándola con la cadena original para determinar si es un palíndromo. Esto implicó crear un archivo Java, escribir código para iterar a través de la cadena en orden inverso y utilizar el método equals() para la comparación.

Luego exploramos el enfoque de dos punteros (two-pointer approach), un método más eficiente para verificar palíndromos que evita crear una nueva cadena invertida. Finalmente, mejoramos nuestra verificación de palíndromos para ignorar mayúsculas/minúsculas y caracteres no alfabéticos, lo que hace que la verificación sea más robusta para escenarios del mundo real.