Programa Java para verificar se uma String é um Palíndromo

Alguns problemas de programação têm o status de clássicos. Normalmente, essas tarefas estão relacionadas à matemática e eles gostam muito de perguntar aos alunos das especialidades de Ciência da Computação, bem como aos candidatos a emprego em entrevistas. Eles são bons porque ajudam a configurar seu pensamento de maneira programadora muito bem, além de treiná-lo. Um desses problemas é verificar se uma string é um palíndromo, e vamos considerá-lo neste artigo.

O que é um palíndromo e por que poder procurá-los

Um palíndromo é um número, combinação de letras, palavra ou texto que lê o mesmo em ambas as direções. Para resumir, um palíndromo pode ser chamado de qualquer conjunto de caracteres que seja simétrico em relação ao seu meio. A palavra é de raízes gregas que derivam literalmente de “correr de volta” (palin é “de novo, de volta” e dromos, “correr”). Palíndromo em Java significa o mesmo que no significado geral. Exemplos de palíndromos:

• 1881
• aaqquqqaa
• pop
• Meio-dia
• nível
• rotador
• minha academia
• Senhora eu sou Adam
• Agora, senhor, uma guerra está vencida!

1881 é um número palíndromo e os outros são strings palíndromos. Neste artigo, veremos palíndromos representados como strings, mas alguns algoritmos são bastante aplicáveis ​​a outros tipos de palíndromos em Java. Por que você pode querer procurar por palíndromos? Na verdade, nem sempre precisamos procurar palíndromos na vida cotidiana. É uma tarefa muito específica. Se nos lembrarmos dos algoritmos de string, com mais frequência na prática, os programadores podem encontrar a busca por uma substring em uma string, e não por palíndromos ou seu número. No entanto, problemas relacionados a palíndromos têm aplicações importantes. A primeira é a programação das olimpíadas. Pode haver tarefas para identificar palíndromos. A segunda aplicação relevante para programadores novatos é a entrevista. Em entrevista técnica, você pode muito bem ser solicitado a escrever rapidamente um programa para verificar se uma string é palíndromo, talvez até mesmo em um pedaço de papel. Bem, na ciência, a aplicação mais prática de encontrar palíndromos são os algoritmos biológicos. Segundo a Wikipedia, a palindromicidade dos compostos biológicos desempenha um papel importante nas propriedades de vários compostos biológicos.

Exemplo de código do algoritmo palíndromo

Vamos pensar. Uma string é uma sequência de caracteres, pode-se dizer, um array de char. Seria mais lógico seguir essa sequência de ambos os lados para o meio e comparar os personagens extremos. Se até chegarmos ao meio todos os nossos personagens forem iguais, então temos um palíndromo. Vamos criar um método booleano validPalindrome(String s) para verificar se String é palíndromo. O código Java está aqui:

public class PalindromeTest1 {

//method to check if a string is palindrome    
public static boolean validPalindrome(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           if (s.charAt(i) != s.charAt(j)) {
               return false;
           }
       }
       return true;
   }

   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!"
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

No método main, verificamos as strings palindrômicas “level”, “cool”, “Madam” e “Now, sir, a war is won!”. Como você pode ver, o primeiro, o terceiro e o quarto são palíndromos, mas o segundo não. O que o programa vai dar? Então, o primeiro é um palíndromo, o segundo não. No entanto, o que há de errado com o terceiro e o quarto? Por que o resultado é falso ? Você provavelmente já adivinhou que o ponto é que alguns caracteres nesta string são maiúsculos e alguns são minúsculos, e para Java M e m são dois caracteres diferentes. Vamos melhorar o programa para levar em conta essa diferença. Aqui está um programa para verificar se uma string é um palíndromo que resolve problemas de letras maiúsculas e minúsculas.

public class PalindromeTest2 {

   //lowercase and uppercase characters should be treated the same:
   public static boolean validPalindrome(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
               return false;
       }
       return true;
   }

   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
        String s4 = "Now, sir, a war is won!"
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

Desta vez, o resultado é mais previsível para nós: Bem... não exatamente previsível. A situação com “Madame” está melhorando, mas com nosso longo e feliz palíndromo “Agora, senhor, uma guerra está ganha!”. É muito fácil, se você lembrar que todos os espaços e símbolos de pontuação são iguais às letras para Java. Portanto, precisamos melhorar nosso algoritmo novamente para corrigir esse descuido. Vamos ensinar nosso programa a ignorar espaços e pontuação. Simplificando, ignoramos todos os caracteres não alfanuméricos. Aqui está o programa palíndromo aprimorado em Java.

public class PalindromeTest3 {

   //in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
   private static boolean isAlphanumeric(char c) {
       return Character.isAlphabetic(c) || Character.isDigit(c);
   }

   public static boolean validPalindromeIgnorePunctuation(String s) {
       for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
           // skip chars we should ignore
           while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
           while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
           // overskipped -> nothing left to validate
           if (i >= j) return true;

           if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
               return false;
       }
       return true;
   }


   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!";
       boolean b1 = validPalindromeIgnorePunctuation(s1);
       boolean b2 = validPalindromeIgnorePunctuation(s2);
       boolean b3 = validPalindromeIgnorePunctuation(s3);
       boolean b4 = validPalindromeIgnorePunctuation(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }

}

Pelo menos o resultado é o que esperávamos dele: Talvez, se você está apenas começando a programar, seja difícil para você entender como funcionam os algoritmos de travessia e comparação de strings. Claro, é melhor lidar com isso, mas você pode escrever uma versão simplificada da própria passagem pela matriz de caracteres, que na verdade é uma string. Você pode usar o método StringBuffer.reverse para verificar se uma string é um palíndromo. Vamos fazer a versão mais simples sem verificar símbolos não alfanuméricos e letras maiúsculas e minúsculas.

public class PalindromeTest5 {

   public static boolean validPalindrome(String s) {

       StringBuffer buffer = new StringBuffer(s);
       buffer.reverse();
       String data = buffer.toString();

       if (s.equals(data)) {
           return true;
       }
       return false;
   }
   public static void main(String[] args) {
       String s1 = "level";
       String s2 = "cool";
       String s3 = "Madam";
       String s4 = "Now, sir, a war is won!";
       boolean b1 = validPalindrome(s1);
       boolean b2 = validPalindrome(s2);
       boolean b3 = validPalindrome(s3);
       boolean b4 = validPalindrome(s4);
       System.out.println("is " + s1 + " a palindrome? " + b1);
       System.out.println("is " + s2 + " a palindrome? " + b2);
       System.out.println("is " + s3 + " a palindrome? " + b3);
       System.out.println("is " + s4 + " a palindrome? " + b4);


   }
}

O resultado é o mesmo do primeiro exemplo Se você quiser, pode melhorar este programa como fizemos no primeiro exemplo. Para reforçar o que você aprendeu, sugerimos que você assista a uma vídeo aula do nosso Curso de Java