Como Verificar se uma String é um Palíndromo em Java

Introdução

Neste laboratório, você aprenderá como verificar se uma string é um palíndromo em Java. Exploraremos diferentes abordagens, começando com o método fundamental de inverter uma string e compará-la com a original.

Com base nisso, você aprenderá uma técnica mais eficiente usando a abordagem de dois ponteiros (two-pointer). Finalmente, aprimoraremos nossa verificação de palíndromo para ignorar maiúsculas e minúsculas e caracteres não-letra, tornando a verificação mais robusta.

Inverter String e Comparar

Nesta etapa, começaremos criando um programa Java simples para inverter uma string e, em seguida, compará-la com a string original. Este é um passo fundamental para entender a manipulação de strings em Java e servirá como um bloco de construção para verificar se uma string é um palíndromo.

Primeiro, vamos criar um novo arquivo Java. No Explorador de Arquivos (File Explorer) no lado esquerdo da WebIDE, clique com o botão direito do mouse no diretório ~/project, selecione "Novo Arquivo" e nomeie-o como StringReverse.java.

Agora, abra o arquivo StringReverse.java no editor e adicione o seguinte 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.");
        }
    }
}

Vamos detalhar este código:

• String originalString = "hello";: Declaramos uma variável String chamada originalString e atribuímos a ela o valor "hello".
• String reversedString = "";: Declaramos uma variável String vazia chamada reversedString. Construiremos a string invertida aqui.
• for (int i = originalString.length() - 1; i >= 0; i--): Este é um loop for que começa do último caractere da originalString (índice length() - 1) e vai até o primeiro caractere (índice 0).
• reversedString += originalString.charAt(i);: Dentro do loop, originalString.charAt(i) obtém o caractere no índice atual i. Em seguida, anexamos este caractere à reversedString.
• System.out.println(...): Estas linhas imprimem as strings original e invertida no console.
• if (originalString.equals(reversedString)): Esta instrução if compara a originalString e a reversedString usando o método equals(). Em Java, você deve usar equals() para comparar o conteúdo das strings, não o operador ==.
• Os blocos if e else imprimem mensagens diferentes com base em se as strings são iguais.

Salve o arquivo StringReverse.java (Ctrl+S ou Cmd+S).

Agora, abra o Terminal na parte inferior da WebIDE. Certifique-se de estar no diretório ~/project. Caso contrário, digite cd ~/project e pressione Enter.

Compile o código Java usando o comando javac:

javac StringReverse.java

Se não houver erros, um arquivo StringReverse.class será criado no diretório ~/project.

Finalmente, execute o programa Java compilado usando o comando java:

java StringReverse

Você deve ver uma saída semelhante a esta:

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

Neste caso, "hello" não é o mesmo de trás para frente, então o programa identifica corretamente isso.

Usar a Abordagem de Dois Ponteiros para Palíndromos

Na etapa anterior, invertemos a string inteira para verificar se era um palíndromo. Embora isso funcione, requer a criação de uma nova string, o que pode ser ineficiente para strings muito longas. Uma abordagem mais eficiente é usar a técnica de dois ponteiros (two-pointer technique).

A técnica de dois ponteiros envolve o uso de dois ponteiros (variáveis que contêm posições de índice) que começam em extremidades diferentes da string e se movem em direção ao centro. Comparamos os caracteres nesses ponteiros. Se eles forem sempre os mesmos à medida que os ponteiros se movem para dentro, a string é um palíndromo. Se encontrarmos qualquer incompatibilidade, não é um palíndromo.

Vamos criar um novo programa Java para implementar isso. No Explorador de Arquivos (File Explorer) à esquerda, crie um novo arquivo chamado PalindromeChecker.java no diretório ~/project.

Abra PalindromeChecker.java e adicione o seguinte 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;
    }
}

Aqui está o que está acontecendo no novo código:

• Criamos um método separado chamado checkPalindrome que recebe uma String como entrada e retorna um boolean (verdadeiro se for um palíndromo, falso caso contrário). Isso torna nosso código mais organizado e reutilizável.
• Dentro de checkPalindrome, inicializamos left com 0 (o índice do primeiro caractere) e right com str.length() - 1 (o índice do último caractere).
• O loop while (left < right) continua enquanto o ponteiro esquerdo estiver à esquerda do ponteiro direito.
• if (str.charAt(left) != str.charAt(right)) compara os caracteres nas posições left e right atuais. Se forem diferentes, sabemos imediatamente que não é um palíndromo e retornamos false.
• Se os caracteres corresponderem, movemos os ponteiros para dentro: left++ incrementa o ponteiro esquerdo e right-- decrementa o ponteiro direito.
• Se o loop terminar sem retornar false, significa que todos os caracteres comparados corresponderam, então a string é um palíndromo e retornamos true.
• No método main, chamamos checkPalindrome com diferentes strings de teste e imprimimos os resultados.

Salve o arquivo PalindromeChecker.java.

Agora, compile e execute o programa no Terminal:

javac PalindromeChecker.java
java PalindromeChecker

Você deve ver a seguinte saída:

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

Isso demonstra como a abordagem de dois ponteiros verifica eficientemente os palíndromos sem inverter a string inteira.

Ignorar Maiúsculas/Minúsculas e Caracteres Não-Letras em Palíndromos

Na etapa anterior, nosso verificador de palíndromos funcionava para strings simples como "madam" e "racecar". No entanto, palíndromos do mundo real geralmente ignoram a capitalização e a pontuação. Por exemplo, "A man, a plan, a canal: Panama" é considerado um palíndromo.

Nesta etapa, aprimoraremos nosso PalindromeChecker para lidar com esses casos, ignorando caracteres que não são letras e tratando letras maiúsculas e minúsculas da mesma forma.

Abra o arquivo PalindromeChecker.java no editor WebIDE. Modificaremos o método checkPalindrome.

Substitua o método checkPalindrome existente pela seguinte versão atualizada:

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

Aqui estão as alterações que fizemos:

• Adicionamos dois loops while dentro do loop principal while (left < right).
• O primeiro loop while interno (while (left < right && !Character.isLetter(str.charAt(left)))) move o ponteiro left para frente, desde que ainda esteja à esquerda do ponteiro right e o caractere no ponteiro left não seja uma letra (!Character.isLetter(...)).
• O segundo loop while interno (while (left < right && !Character.isLetter(str.charAt(right)))) move o ponteiro right para trás, desde que ainda esteja à esquerda do ponteiro right e o caractere no ponteiro right não seja uma letra.
• A comparação if (left < right && Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) agora inclui duas verificações importantes:
  • left < right: Isso garante que comparemos os caracteres somente se os ponteiros não tiverem se cruzado após ignorar não-letras.
  • Character.toLowerCase(...): Isso converte ambos os caracteres para minúsculas antes de compará-los, ignorando efetivamente a capitalização.
• Se os caracteres (após a conversão para minúsculas) não corresponderem, retornamos false.
• Se eles corresponderem, movemos ambos os ponteiros para dentro (left++, right--) para verificar o próximo par de caracteres.

Agora, vamos modificar o método main para testar com uma string que inclui espaços, pontuação e capitalização mista. Substitua os casos de teste existentes no método main por isto:

    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.");
        }
    }

Salve o arquivo PalindromeChecker.java.

Compile e execute o programa atualizado no Terminal:

javac PalindromeChecker.java
java PalindromeChecker

Você deve ver a seguinte saída, identificando corretamente os palíndromos, mesmo com caracteres que não são letras e capitalização mista:

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

Você aprimorou com sucesso seu verificador de palíndromos para lidar com strings mais complexas!

Resumo

Neste laboratório, aprendemos como verificar se uma string é um palíndromo em Java. Começamos implementando um método para inverter uma string e compará-la com a string original para determinar se é um palíndromo. Isso envolveu a criação de um arquivo Java, a escrita de código para iterar pela string em ordem inversa e o uso do método equals() para comparação.

Em seguida, exploramos a abordagem de dois ponteiros (two-pointer approach), um método mais eficiente para a verificação de palíndromos que evita a criação de uma nova string invertida. Finalmente, aprimoramos nossa verificação de palíndromos para ignorar maiúsculas/minúsculas e caracteres que não são letras, tornando a verificação mais robusta para cenários do mundo real.