Palavras Palíndromas

Um palíndromo é uma palavra que pode ser lida tanto da esquerda para a direita como da direta para a esquerda. Por exemplo:

"A man, a plan, a canal, Panama!"

"Anotaram a data da maratona."

Vamos agora dar uma definição indutiva para o problema:

Idéia indutiva

• Caso Base: uma palavra com 1 caractere é um palíndromo.
• Hipótese de indução: vamos supor que a palavra sem o primeiro e o último caractere é um palíndromo.
• Caso Geral: Se o primeiro e o último caractere forem iguais e a hipótese de indução for verdadeira, então a palavra é um palíndromo.

E mais uma vez, se seguirmos a idéia indutiva, o algoritmo surge de forma imediata!

• Implementação em Haskell

palindromo :: String -> Bool
palindromo [] = True
palindromo [a] = True
palindromo (x:xs) = (x == last xs) && (palindromo elem)
    where
        newlen = (length xs) – 1
        elem = take newlen xs

• Implementação em C++ (versão iterativa)

bool palindromo(int n, char s[]){

    int i = 0, j = n - 1;
    while(i < j){
         if(s[i] != s[j])
             return false;
         i++;
         j--;
    }
    return true;
}