Artigo original: Two Ways to Check for Palindromes in JavaScript

Este artigo tem como base no projeto de algoritmos e estruturas de dados em JavaScript do FreeCodeCamp, "Verificador de palíndromo".

Um palíndromo é uma palavra, expressão, número ou outra sequência de caracteres que pode ser lido tanto do começo até o fim, quanto do fim ao começo com o mesmo resultado. A palavra "palíndromo" foi criada pelo dramaturgo inglês Ben Jonson no século XVII, e vem da raiz grega palin ("novamente") e dromos ("caminho ou direção"). — fonte: Wikipédia

Neste artigo, explicarei duas abordagens, a primeira com funções integradas do JavaScript e a segunda usando um laço for.

Desafio de algoritmos

Retorne true se a string fornecida for um palíndromo. Caso contrário, retorne false.
Um palíndromo é uma palavra ou frase que é dita da mesma maneira na ordem natural que na ordem inversa, ignorando pontuação, capitalização e espaçamento.
Observação: você precisará remover todos os caracteres não alfanuméricos (pontuação, espaços e símbolos) e transforme tudo na mesma capitalização (letra em minúsculo ou maiúsculo) para verificar se determinada palavra ou frase é um palíndromo.
Vamos passar strings em diferentes formatos, como racecar, RaceCarar e race CAR entre outros.
function palindrome(str) {
  return true;
}
palindrome("eye");

Casos de teste fornecidos

  • palindrome("race car") deve retornar true
  • palindrome("not a palindrome") deve retornar false
  • palindrome("A man, a plan, a canal. Panama") deve retornar true
  • palindrome("never odd or even") deve retornar true
  • palindrome("nope") deve retornar false
  • palindrome("almostomla") deve retornar false
  • palindrome("My age is 0, 0 si ega ym.") deve retornar true
  • palindrome("1 eye for of 1 eye.") deve retornar false
  • palindrome("0_0 (: /-\ :) 0–0") deve retornar true

De quais expressões regulares precisamos para passar no último caso de teste?

Expressões regulares são padrões usados para corresponder a combinações de caracteres em strings.

Quando a pesquisa por uma correspondência exige algo mais que uma correspondência direta, o padrão inclui caracteres especiais.

Para passar no último caso de teste, podemos usar duas expressões regulares:

/[^A-Za-z0–9]/g  ou

/[\W_]/g

\W remove todos os caracteres não alfanuméricos:

  • \W corresponde a todos os caracteres que não sejam alfabéticos
  • \W é equivalente a [^A-Za-z0–9_]
  • \W corresponde a tudo o que não estiver envolvido nos colchetes

O que isso significa?

[^A-Z] corresponde a tudo o que não estiver envolvido entre A e Z

[^a-z] corresponde a tudo o que não estiver envolvido entre a e z

[^0-9] corresponde a tudo o que não estiver envolvido entre 0 e 9

[^_] corresponde a tudo o que não for _

Em nosso caso de teste, contudo, precisamos que palindrome("0_0 (: /-\ :) 0–0") retorne true, o que significa que "_(: /-\ :)–" precisa ter correspondência.

Precisamos adicionar "_" para passar nesse caso de teste específico.

Agora, temos "\W_"

Também precisamos adicionar a flag g para a pesquisa global.

Por fim, temos "/[\W_]/g"
/[\W_]/g foi usado para fins puramente demonstrativos para mostrar como funcionam as RegExp (expressões regulares). /[^A-Za-z0–9]/g é a RegExp mais fácil de se utilizar.

1. Verificador de palíndromo com funções integradas

Para essa solução, usaremos vários métodos:

  • O método toLowerCase() retornará o valor da string que o chama convertido para letras minúsculas.
  • O método replace() retornará uma nova string com alguma ou todas as correspondências substituídas por aquilo que sugerirmos. Usaremos uma das RegExp que acabamos de criar.
  • O método split() divide um objeto de string em um array de strings separando-a em substrings.
  • O método reverse() inverte um array. O primeiro elemento do array se torna o último e o último se torna o primeiro.
  • O método join() reúne todos os elementos do array em uma string.
function palindrome(str) {
  // Passo 1. Coloca a string em letras minúsculas e usa o RegExp para remover caracteres indesejados dela
  var re = /[\W_]/g; // ou var re = /[^A-Za-z0-9]/g;
  
  var lowRegStr = str.toLowerCase().replace(re, '');
  // str.toLowerCase() = "A man, a plan, a canal. Panama".toLowerCase() = "a man, a plan, a canal. panama"
  // str.replace(/[\W_]/g, '') = "a man, a plan, a canal. panama".replace(/[\W_]/g, '') = "amanaplanacanalpanama"
  // var lowRegStr = "amanaplanacanalpanama";
     
  // Passo 2. Usa os mesmos métodos de encadeamento com funções integradas di artigo anterior 'Três modos de inverter uma string em JavaScript'
  var reverseStr = lowRegStr.split('').reverse().join(''); 
  // lowRegStr.split('') = "amanaplanacanalpanama".split('') = ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"]
  // ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"].reverse() = ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"]
  // ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"].join('') = "amanaplanacanalpanama"
  // Emtão, "amanaplanacanalpanama".split('').reverse().join('') = "amanaplanacanalpanama";
  // E var reverseStr = "amanaplanacanalpanama";
   
  // Passo 3. Verifica se reverseStr é estritamente igual a lowRegStr e retorna um booleano
  return reverseStr === lowRegStr; // "amanaplanacanalpanama" === "amanaplanacanalpanama"? => true
}
 
palindrome("A man, a plan, a canal. Panama");

Sem os comentários:

function palindrome(str) {
  var re = /[\W_]/g;
  var lowRegStr = str.toLowerCase().replace(re, '');
  var reverseStr = lowRegStr.split('').reverse().join(''); 
  return reverseStr === lowRegStr;
}
palindrome("A man, a plan, a canal. Panama");

2. Verificador de palíndromo com um laço FOR

A indexação da metade (len/2) tem benefícios ao processar strings grandes. Verificamos o final de cada parte e dividimos o número de iterações dentro do laço FOR pela metade.

function palindrome(str) {
 // Passo 1. A primeira parte é a mesma que a anterior
 var re = /[^A-Za-z0-9]/g; // ou var re = /[\W_]/g;
 str = str.toLowerCase().replace(re, '');

 // Passo 2. Criar o laço FOR
 var len = str.length; // var len = "A man, a plan, a canal. Panama".length = 30
 
 for (var i = 0; i < len/2; i++) {
   if (str[i] !== str[len - 1 - i]) { // Enquanto os caracteres de cada parte corresponderem, o laço FOR continuará
       return false; // Quando os caracteres pararem de corresponder, é retornado false e saímos do laço FOR
   }
   /* Aqui, len/2 = 15
      Para cada iteração: i = ?    i < len/2    i++    if(str[i] !== str[len - 1 - i])?
      1ª iteração:        0        sim         1     if(str[0] !== str[15 - 1 - 0])? => if("a"  !==  "a")? // false
      2ª iteração:        1        sim         2     if(str[1] !== str[15 - 1 - 1])? => if("m"  !==  "m")? // false      
      3ª iteração:        2        sim         3     if(str[2] !== str[15 - 1 - 2])? => if("a"  !==  "a")? // false  
      4ª iteração:        3        sim         4     if(str[3] !== str[15 - 1 - 3])? => if("n"  !==  "n")? // false  
      5ª iteração:        4        sim         5     if(str[4] !== str[15 - 1 - 4])? => if("a"  !==  "a")? // false
      6ª iteração:        5        sim         6     if(str[5] !== str[15 - 1 - 5])? => if("p"  !==  "p")? // false
      7ª iteração:        6        sim         7     if(str[6] !== str[15 - 1 - 6])? => if("l"  !==  "l")? // false
      8ª iteração:        7        sim         8     if(str[7] !== str[15 - 1 - 7])? => if("a"  !==  "a")? // false
      9ª iteração:        8        sim         9     if(str[8] !== str[15 - 1 - 8])? => if("n"  !==  "n")? // false
     10ª iteração:        9        sim        10     if(str[9] !== str[15 - 1 - 9])? => if("a"  !==  "a")? // false
     11ª iteração:       10        sim        11    if(str[10] !== str[15 - 1 - 10])? => if("c" !==  "c")? // false
     12ª iteração:       11        sim        12    if(str[11] !== str[15 - 1 - 11])? => if("a" !==  "a")? // false
     13ª iteração:       12        sim        13    if(str[12] !== str[15 - 1 - 12])? => if("n" !==  "n")? // false
     14ª iteração:       13        sim        14    if(str[13] !== str[15 - 1 - 13])? => if("a" !==  "a")? // false
     15ª iteração:       14        sim        15    if(str[14] !== str[15 - 1 - 14])? => if("l" !==  "l")? // false
     16ª iteração:       15        não               
    Fim do laço FOR*/
 }
 return true; // Se as duas partes são estritamente iguais, o retorno é true => A string é um palíndromo
}

palindrome("A man, a plan, a canal. Panama");

Sem comentários:

function palindrome(str) {
 var re = /[^A-Za-z0-9]/g;
 str = str.toLowerCase().replace(re, '');
 var len = str.length;
 for (var i = 0; i < len/2; i++) {
   if (str[i] !== str[len - 1 - i]) {
       return false;
   }
 }
 return true;
}
palindrome("A man, a plan, a canal. Panama");

Espero que você tenha achado esse artigo útil. Ele é parte da sequência de artigos da autora "Como resolver os algoritmos do FCC" nos Desafios de algoritmos do FreeCodeCamp. Nesses artigos, a autora propõe várias soluções e explica o passo a passo do que ocorre internamente.

Two ways to confirm the ending of a String in JavaScript
Neste artigo, ainda em inglês, a autora explica como resolver o desafio "Confirmar o final".

Three Ways to Reverse a String in JavaScript
Neste artigo, ainda em inglês, a autora explica como resolver o desafio "Inverter uma string".

Three Ways to Factorialize a Number in JavaScript
Neste artigo, ainda em inglês, a autora explica como resolver o desafio "Fatorar um número".

Three Ways to Find the Longest Word in a String in JavaScript
Neste artigo, ainda em inglês, a autora explica como resolver o desafio  "Encontrar a palavra mais longa em uma string".

Three Ways to Title Case a Sentence in JavaScript
Neste artigo, ainda em inglês, a autora explica como resolver o desafio "Capitalizar o título de uma frase".

Three ways you can find the largest number in an array using JavaScript
Neste artigo, ainda em inglês, a autora explica como resolver o desafio "Retornar os maiores números em arrays"

Se tiver sua própria solução ou sugestões, sinta-se à vontade para compartilhá-las por meio de comentários.

Você também pode seguir a autora no Medium, no Twitter, no Github e no LinkedIn ;-)

‪#‎StayCurious‬, ‪#‎KeepOnHacking‬, ‪#‎MakeItHappen‬!

Recursos utilizados