Anagramas

Hooray! Este artigo marca o último desafio de manipulação de cordas nesta secção deste curso. Percorremos um longo caminho!

Neste desafio, consideramos duas formas de detectar anagramas em JavaScript.

O que é um anagrama?

Diz-se que uma palavra é um anagrama de outra quando pode ser formada rearranjando as letras da outra palavra usando cada letra apenas uma vez. Por exemplo, ouvir é um anagrama de silêncio.

Vamos nos ocupar, devemos?

Você já deve ter o seu ambiente de desenvolvimento configurado para este curso. Atualize seu repositório clonado executando o comando git pull. Dentro da pasta Beginner, navegue até a pasta isAnagram. O nosso trabalho para este desafio será feito aqui. Certifique-se de seguir no arquivoindex-START.js.

O Desafio

Dado duas cordas, escreva um algoritmo para verificar se elas são anagramas uma da outra. Retorne verdadeiro se passarem no teste e falso se não passarem. E.g

isAnagram('silent', 'listen') // should return true

Pensamento Algorítmico

Ao resolver este desafio, escrevemos uma função que aceitaria dois parâmetros, ou seja, as duas strings a serem comparadas.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

Com a função, comparamos as duas palavras para ver se elas contêm os mesmos caracteres usados o mesmo número de vezes. Para evitar erros, higienizamos a string eliminando assim caracteres e espaços indesejados, uma vez que estes não são letras do alfabeto.

Tambem convertemos todos os caracteres para um caso de letra comum antes de realizar qualquer comparação para evitar erros devido à capitalização variável. Verificar se ambas as palavras têm o mesmo comprimento também é muito importante, pois este é um fator primário para uma comparação válida.

Vamos fazer isto.

Implementação de código

Passamos agora a considerar duas formas de implementar a nossa solução seguindo a nossa lógica algorítmica acima. Elas são:

• Comparação Direta
• Comparação de Mapa de Caracteres

Comparação Direta

Nesta abordagem, nós definimos uma função que aceita dois parâmetros, ou seja, as duas cadeias de caracteres a serem comparadas. Vamos então limpar ambas as strings para assegurar que estamos comparando apenas letras e num caso comum.

Limpeza da StringPara limpar a string, criamos uma função sanitizeString. Esta função aceita a string a ser higienizada como um parâmetro e usa os métodos .toLowerCase(), .replace(), .split(), .sort() e .join() para manipular a string como mostrado abaixo:

const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join('');}

Vamos quebrar um pouco as coisas:

• Primeiro, convertemos a string inteira para minúsculas usando o método .toLowerCase().
• Próximo, usamos o método .replace() para procurar através da string usando o padrão de expressão regular especificado e substituir cada caractere não alfabético por uma string vazia. Isto deixa-nos apenas com letras. Sem espaços, sem símbolos!
• Next, chamamos .split() para dividir a string em um array de caracteres.
• Usando o método .sort(), ordenamos as letras (elementos) dentro do array em ordem alfabética.
• E finalmente, juntamos o array de letras agora em ordem alfabética para formar uma string mais uma vez.

Esta string é o que retornamos como a string sanitized.

Suave!** Certo?**

Comparar as Strings SanitizedSanitizedSanitized a string como feito acima é talvez a parte mais complicada desta solução. A seguir, nós simplesmente limpamos as cordas recebidas usando a função sanitizeString e comparamos os resultados. Se ambas as strings combinarem, retornamos true significando que elas passam como anagramas. Se não coincidirem, retornamos false significando que não são.

Veja a solução completa abaixo:

function isAnagram(stringA, stringB) { const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join(''); } return sanitizeString(stringA) == sanitizeString(stringB)}

Um down!** Vamos ficar mais estranhos! 😈**

Como você verá, a abordagem que agora vamos considerar segue um procedimento mais passo a passo para resolver o problema.

Comparação do Mapa de Caracteres

Nesta abordagem, nós primeiro geramos um mapa de caracteres usando a nossa função createCharMap.

O que é um mapa de caracteres?

Como usado neste contexto , um objeto de mapa de caracteres é um objeto que mapeia cada caractere em uma string para o número de vezes que ele ocorre dentro da string.

Criando o Mapa de CaracteresNa nossa função createCharMap abaixo, usamos um for…de loop para iterar através de cada caractere da string recebida.

function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap}

Para cada caractere, verificamos se o caractere já existe como propriedade no mapa de caracteres charMap usando o método .hasOwnProperty(). Se existir, incrementamos o seu valor e se não existir, adicionamos o caracter como propriedade e definimos o seu valor como 1.

No final, retornamos charMap que é o objeto character map.

Comparando Character MapsAgora que temos uma forma de gerar os mapas de caracteres, o próximo passo será comparar os mapas de caracteres para ambas as strings como mostrado na solução completa abaixo:

function isAnagram(stringA, stringB) { function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap } if (stringA.length === stringB.length) { let stringAMap = createCharMap(stringA) let stringBMap = createCharMap(stringB) for (let char in stringAMap) { if (stringAMap !== stringBMap) { return false } } return true } else { return false }}

Note que primeiro verificamos se o comprimento de ambas as strings é igual. Se não forem, retornamos false, pois este é um indicador de que elas nunca poderão ser anagramas. Se forem no entanto, vamos mais longe para gerar seus mapas de caracteres armazenados como variáveis stringAMap e stringBMap.

Next, usamos o for…in loop para comparar cada caractere e valor em stringAMap com o valor correspondente do caractere em stringBMap. Se algum valor não corresponder, retornamos false como uma indicação de que as strings não são anagramas. Entretanto, se todos os valores corresponderem, o teste é passado e retornamos true como uma indicação de que as strings testadas são anagramas de fato.

Fizemo-lo. Uma implementação mais longa de fato, mas definitivamente mais explicativa.

Vamos executar nossos testes agora, vamos?

>

Testes de Correcção com Jest

Para testar cada solução acima, corra o seguinte comando do seu terminal:

npm run test isAnagram

• Comparação Directa

• >

  Comparação de Caracteres do Mapa

Parece que nos saímos sempre bem! Passamos todos os testes.

>

Testes de desempenho com JSPerf

Aqui, fazemos um teste de desempenho para determinar qual solução é mais rápida. Encontre uma captura de tela do resultado abaixo:

Do resultado, observamos que:

A implementação mais rápida é a abordagem de Comparação de Mapas de Caracteres e o método de Comparação Direta embora conciso é aproximadamente 52% mais lento.

**Surprising não é? A métrica nunca mente!**

Aplicação prática

Os algoritmos explorados acima podem ser aplicados de várias maneiras. Estas incluem:

• Encryption
• Geração de palavras-passe
• Tempo de impressão confiável
• Entrevistas de codificação
• Geração de mnemônicos
• Jogos de palavras
  

  Conclusão

Embora considerando as técnicas e conceitos explorados acima, aprendemos maneiras valiosas de manipular as cordas para determinar se são anagramas. Também exploramos várias áreas nas quais esse conhecimento pode ser utilizado diretamente.

Após executarmos nossos testes de desempenho podemos agora concluir que a abordagem mais ótima para resolver este problema é o método de Comparação de Mapa de Caracteres.

Leitura adicional

Para aprender mais sobre os conceitos e técnicas destacados acima, você pode usar os seguintes links:

• Expressões Regulares
• .replace()
• .split()
• .sort()

>

• .join()
• .hasOwnProperty()
• >Para…de vs…em loop

Veja-o no próximo conjunto de artigos focados em algoritmos de manipulação de array! ✌🏿

Como este artigo? Siga @worldclassdev no Twitter