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
Retornetrue
se a string fornecida for um palíndromo. Caso contrário, retornefalse
.
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, comoracecar
,RaceCarar
erace 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!