1
htlw
2 min de leitura ·

Algoritmo para verificar se um texto é um palíndromo

FAQ

  • O que é um palíndromo?
    R: Um texto que, normalizado (tudo minúsculo, sem espaços, pontuações, acentos gráficos etc.), é escrito da mesma forma ao contrário. Ex.: "Ovo", "Mirim", "Subi no ônibus" [...]

  • Por que eu deveria saber verificar um palíndromo?
    R: Para se preparar para uma prova (seja técnica em uma entrevista de emprego ou acadêmica em uma faculdade), estudar como estruturas de dados funcionam em determinada linguagem de programação ou simplesmente porquê sim.

  • Essa é a única forma?
    R: Não, assim como quase tudo em programação.

Premissa:

Dada uma sequência de caracteres já normalizada, preciso realizar continuamente, nesta ordem, o seguinte procedimento sobre o texto:

  1. Obter o valor do primeiro e do último caractere - ainda não comparados -, que vou chamar de ponteiro, para não repetir "valor ainda não comparado mais à esquerda" e "valor ainda não comparado mais à direita" toda vez;
  2. Verificar se eles são diferentes;
  3. Caso sim, fim do algoritmo: o texto não é um palíndromo;
  4. Caso não, devo avançar o ponteiroEsquerda e recuar o ponteiroDireita, e executar os passos 1, 2 e 3 novamente, até os ponteiros convergirem no centro.

Exemplo 1

Input: "grama"

(g)ram(a) → g <> a = verdadeiro

Output: a palavra "grama" não é um palíndromo!

Exemplo 2

Input: "radar"

(r)ada(r) → r <> r = falso

r(a)d(a)r → a <> a = falso

ra(d)ar → não há mais caracteres para comparar; a palavra "radar" é um palíndromo!

Implementação em pseudocódigo comentada:

algoritmo verificaSeÉPalindromo;
função éPalindromo(texto: caractere)
    // normaliza texto antes de iniciar
    caractere textoNormalizado = normalizarTexto(texto);

    // inicializa ponteiros
    inteiro ponteiroEsquerda = 0; // primeiro caractere
    inteiro ponteiroDireita = textoNormalizado.comprimento() - 1; // último caractere

    // enquanto os ponteiros não convergirem no centro
    enquanto (ponteiroEsquerda < ponteiroDireita) faça:
        // se o valor mais à esquerda for diferente do valor mais à direita
        se (textoNormalizado[ponteiroEsquerda] <> textoNormalizado[ponteiroDireita]) então:
            // o texto não é um palíndromo, finaliza o algoritmo
            retorne falso;
        // se forem iguais, aproximam-se os ponteiros do centro
        ponteiroEsquerda = ponteiroEsquerda + 1;
        ponteiroDireita = ponteiroDireita - 1;
    fimEnquanto;

    // se os ponteiros chegarem ao centro e não houver mais valores para comparar,
    // quer dizer que o texto é um palíndromo
    retorne verdadeiro;
fimFunção;

escreva(éPalindromo("grama")) // output: falso
escreva(éPalindromo("radar")) // output: verdadeiro
fimAlgoritmo;

é isso, agora você sabe uma das lógicas de se verificar se um determinado texto é um palíndromo.

Carregando publicação patrocinada...