Anagramas

¡Hola! Este artículo marca el último reto de manipulación de cadenas en esta sección de este curso. Hemos recorrido un largo camino!

En este reto, consideramos dos formas de detectar anagramas en JavaScript.

¿Qué es un anagrama?

Se dice que una palabra es un anagrama de otra cuando se puede formar reordenando las letras de la otra palabra usando cada letra sólo una vez. Por ejemplo, «listen» es un anagrama de «silent».

Vamos a ponernos manos a la obra,

Ya deberías tener configurado tu entorno de desarrollo para este curso. Actualiza tu repositorio clonado ejecutando el comando git pull. Dentro de la carpeta Beginner, navega hasta la carpeta isAnagram. Nuestro trabajo para este desafío se hará aquí. Asegúrate de seguir en el archivoindex-START.js.

El reto

Dadas dos cadenas, escribe un algoritmo para comprobar si son anagramas entre sí. Devuelve verdadero si pasan la prueba y falso si no lo hacen. E.g

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

Pensamiento Algorítmico

En la resolución de este reto, escribimos una función que acepte dos parámetros, es decir, las dos cadenas a comparar.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

Dentro de la función, comparamos ambas palabras para ver si contienen los mismos caracteres utilizados el mismo número de veces. Para evitar errores, saneamos la cadena deshaciéndonos así de los caracteres no deseados y de los espacios ya que no son letras del alfabeto.

También convertimos todos los caracteres a una letra común antes de realizar cualquier comparación para evitar errores debidos a la variación de las mayúsculas. Comprobar que ambas palabras tienen la misma longitud es también muy importante ya que es un factor primordial para una comparación válida.

Hagamos esto.

Implementación del código

Ahora consideraremos dos formas de implementar nuestra solución siguiendo nuestra lógica algorítmica anterior. Son:

• Comparación directa
• Comparación por mapa de caracteres

Comparación directa

En este enfoque, definimos una función que acepta dos parámetros, es decir, las dos cadenas a comparar. A continuación, pasar a limpiar ambas cadenas para asegurarse de que estamos comparando sólo las letras y en un caso común.

Limpiar la cadenaPara limpiar la cadena, creamos una función sanitizeString. Esta función acepta la cadena a limpiar como parámetro y utiliza los métodos .toLowerCase(), .replace(), .split(), .sort() y .join() para manipular la cadena como se muestra a continuación:

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

Desglosemos un poco las cosas:

• Primero, convertimos toda la cadena a minúsculas utilizando el método .toLowerCase().
• Luego, usamos el método .replace() para buscar en la cadena usando el patrón de expresión regular especificado y reemplazamos cada carácter no alfabético con una cadena vacía. Esto nos deja con sólo letras. Sin espacios ni símbolos.
• A continuación, llamamos a .split() para dividir la cadena en una matriz de caracteres.
• Usando el método .sort(), ordenamos las letras (elementos) dentro de la matriz en orden alfabético.
• Y finalmente, unimos la matriz de letras ahora ordenada alfabéticamente para formar una cadena una vez más.

Esta cadena es la que devolvemos como cadena desinfectada.

¡Suave!** ¿Verdad?**

Comparando las cadenas desinfectadasLa desinfección de la cadena como se ha hecho anteriormente es quizás la parte más complicada de esta solución. A continuación, simplemente limpiamos las cadenas recibidas utilizando la función sanitizeString y comparamos los resultados. Si ambas cadenas coinciden, devolvemos true significando que pasan como anagramas. Si no coinciden, devolvemos false significando que no lo son.

Vea la solución completa a continuación:

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

¡Una menos!** ¡Pongámonos más raros! 😈**

Como verás, el enfoque que consideraremos ahora sigue un procedimiento más gradual para resolver el problema.

Comparación de mapas de caracteres

En este enfoque, primero generamos un mapa de caracteres utilizando nuestra función createCharMap.

¿Qué es un mapa de caracteres?

Como se utiliza en este contexto , un objeto de mapa de caracteres es un objeto que asigna cada carácter de una cadena al número de veces que aparece dentro de la cadena.

Creando el mapa de caracteresEn nuestra función createCharMap a continuación, utilizamos un bucle for…of para iterar a través de cada carácter de la cadena recibida.

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

Por cada carácter, comprobamos si el carácter ya existe como una propiedad en el mapa de caracteres charMap utilizando el método .hasOwnProperty(). Si existe, incrementamos su valor y si no existe, añadimos el carácter como propiedad y ponemos su valor a 1.

Al final, devolvemos charMap que es el objeto mapa de caracteres.

Comparación de mapas de caracteresAhora que tenemos una forma de generar los mapas de caracteres, el siguiente paso será comparar los mapas de caracteres de ambas cadenas como se muestra en la solución completa de abajo:

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 }}

Nota que primero comprobamos si la longitud de ambas cadenas es igual. Si no lo son, devolvemos false ya que esto es un indicador de que nunca pueden ser anagramas. Sin embargo, si lo son, vamos más allá para generar sus mapas de caracteres almacenados como variables stringAMap y stringBMap.

A continuación, utilizamos el bucle for…in para comparar cada carácter y valor en stringAMap con el valor correspondiente del carácter en stringBMap. Si algún valor no coincide, devolvemos false como indicación de que las cadenas no son anagramas. Sin embargo, si todos los valores coinciden, la prueba es superada y devolvemos true como indicación de que las cadenas probadas son efectivamente anagramas.

Lo conseguimos. Una implementación más larga, pero definitivamente más explicativa.

Ejecutamos ahora nuestras pruebas, ¿quieres?

Probando la corrección con Jest

Para probar cada una de las soluciones anteriores, ejecuta el siguiente comando desde tu terminal:

npm run test isAnagram

• Comparación directa

• Comparación de mapas de caracteres

¡Parece que siempre lo hacemos bien! Pasamos todas las pruebas.

Probando el rendimiento con JSPerf

Aquí, ejecutamos una prueba de rendimiento para determinar qué solución es más rápida. Encuentra una captura de pantalla del resultado a continuación:

Del resultado, observamos que:

La implementación más rápida es el enfoque de Comparación de Mapa de Caracteres y el método de Comparación Directa aunque conciso es aproximadamente un 52% más lento.

**Sorprendente, ¿verdad? Aunque las métricas nunca mienten!

Aplicación práctica

Los algoritmos explorados anteriormente pueden aplicarse de varias maneras. Entre ellas:

• Encriptación
• Generación de contraseñas
• Sellado de tiempo de confianza
• Codificación de entrevistas
• Generación de mnemónicos
• Juegos de palabras
  

  Conclusión

Al considerar las técnicas y conceptos explorados anteriormente, hemos aprendido formas valiosas de manipular cadenas para determinar si son anagramas. También hemos explorado varias áreas en las que este conocimiento puede ser utilizado directamente.

Después de ejecutar nuestras pruebas de rendimiento podemos concluir que el enfoque más óptimo para resolver este problema es el método de comparación de mapas de caracteres.

Las lecturas adicionales

Para aprender más sobre los conceptos y técnicas destacadas anteriormente, puede utilizar los siguientes enlaces:

• Expresiones regulares
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in loop

¡Nos vemos en la próxima serie de artículos centrados en algoritmos de manipulación de arrays!✌🏿

¿Te gusta este artículo? Sigue a @worldclassdev en Twitter