1. Información general
Según Wikipedia, un anagrama es una palabra o frase formada reordenando las letras de una palabra o frase diferente.
Podemos generalizar esto en el procesamiento de cadenas diciendo que un anagrama de una cadena es otra cadena con exactamente la misma cantidad de cada carácter, en cualquier orden .
En este tutorial, veremos cómo detectar anagramas de cadena completa donde la cantidad de cada carácter debe ser igual, incluidos los caracteres no alfabéticos como espacios y dígitos. Por ejemplo, "! Bajo en sal!" y "búhos-lat !!" se considerarían anagramas ya que contienen exactamente los mismos caracteres.
2. Solución
Comparemos algunas soluciones que pueden decidir si dos cadenas son anagramas. Cada solución comprobará al principio si las dos cadenas tienen el mismo número de caracteres. Esta es una forma rápida de salir antes, ya que las entradas con diferentes longitudes no pueden ser anagramas .
Para cada posible solución, veamos la complejidad de la implementación para nosotros como desarrolladores. También veremos la complejidad del tiempo para la CPU, usando la notación O grande.
3. Verifique por clasificación
Podemos reorganizar los caracteres de cada cadena ordenando sus caracteres, lo que producirá dos matrices normalizadas de caracteres.
Si dos cadenas son anagramas, sus formas normalizadas deberían ser las mismas.
En Java, primero podemos convertir las dos cadenas en matrices char [] . Luego podemos ordenar estas dos matrices y verificar la igualdad:
boolean isAnagramSort(String string1, String string2) { if (string1.length() != string2.length()) { return false; } char[] a1 = string1.toCharArray(); char[] a2 = string2.toCharArray(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2); } Esta solución es fácil de entender e implementar. Sin embargo, el tiempo de ejecución total de este algoritmo es O (n log n) porque ordenar una matriz de n caracteres lleva O (n log n) tiempo.
Para que el algoritmo funcione, debe hacer una copia de ambas cadenas de entrada como matrices de caracteres, usando un poco de memoria extra.
4. Verifique contando
Una estrategia alternativa es contar el número de ocurrencias de cada carácter en nuestras entradas. Si estos histogramas son iguales entre las entradas, entonces las cadenas son anagramas.
Para ahorrar un poco de memoria, creemos solo un histograma. Incrementaremos los recuentos de cada carácter en la primera cadena y disminuiremos el recuento de cada carácter en la segunda. Si las dos cadenas son anagramas, el resultado será que todo se equilibre en 0.
El histograma necesita una tabla de recuentos de tamaño fijo con un tamaño definido por el tamaño del juego de caracteres. Por ejemplo, si solo usamos un byte para almacenar cada carácter, entonces podemos usar un tamaño de matriz de conteo de 256 para contar la ocurrencia de cada carácter:
private static int CHARACTER_RANGE= 256; public boolean isAnagramCounting(String string1, String string2) { if (string1.length() != string2.length()) { return false; } int count[] = new int[CHARACTER_RANGE]; for (int i = 0; i < string1.length(); i++) { count[string1.charAt(i)]++; count[string2.charAt(i)]--; } for (int i = 0; i < CHARACTER_RANGE; i++) { if (count[i] != 0) { return false; } } return true; }Esta solución es más rápida con la complejidad temporal de O (n) . Sin embargo, necesita espacio adicional para la matriz de conteo. Con 256 enteros, para ASCII eso no está tan mal.
Sin embargo, si necesitamos aumentar CHARACTER_RANGE para admitir conjuntos de caracteres de múltiples bytes como UTF-8, esto consumiría mucha memoria. Por lo tanto, solo es realmente práctico cuando la cantidad de caracteres posibles está en un rango pequeño.
Desde el punto de vista del desarrollo, esta solución contiene más código para mantener y hace menos uso de las funciones de la biblioteca de Java.
5. Verifique con MultiSet
Podemos simplificar el proceso de conteo y comparación utilizando MultiSet . MultiSet es una colección que admite la igualdad independiente del orden con elementos duplicados. Por ejemplo, los conjuntos múltiples {a, a, b} y {a, b, a} son iguales.
Para usar Multiset , primero debemos agregar la dependencia de Guava a nuestro archivo pom.xml del proyecto :
com.google.guava guava 28.1-jre Convertiremos cada una de nuestras cadenas de entrada en un MultiSet de caracteres. Luego comprobaremos si son iguales:
boolean isAnagramMultiset(String string1, String string2) { if (string1.length() != string2.length()) { return false; } Multiset multiset1 = HashMultiset.create(); Multiset multiset2 = HashMultiset.create(); for (int i = 0; i < string1.length(); i++) { multiset1.add(string1.charAt(i)); multiset2.add(string2.charAt(i)); } return multiset1.equals(multiset2); } Este algoritmo resuelve el problema en O (n) tiempo sin tener que declarar una gran matriz de conteo.
Es similar a la solución de conteo anterior. Sin embargo, en lugar de usar una tabla de tamaño fijo para contar, aprovechamos la clase MutlitSet para simular una tabla de tamaño variable, con un recuento para cada carácter.
El código de esta solución hace más uso de las capacidades de la biblioteca de alto nivel que nuestra solución de conteo.
6. Anagrama basado en letras
Los ejemplos hasta ahora no se adhieren estrictamente a la definición lingüística de un anagrama. Esto se debe a que consideran los caracteres de puntuación como parte del anagrama y distinguen entre mayúsculas y minúsculas.
Adaptemos los algoritmos para habilitar un anagrama basado en letras. Consideremos únicamente la reordenación de letras que no distinguen entre mayúsculas y minúsculas, independientemente de otros caracteres, como espacios en blanco y signos de puntuación. Por ejemplo, "Un punto decimal" y "Soy un punto en su lugar". serían anagramas el uno del otro.
Para resolver este problema, primero podemos preprocesar las dos cadenas de entrada para filtrar los caracteres no deseados y convertir las letras en minúsculas. Luego, podemos usar una de las soluciones anteriores (por ejemplo, la solución MultiSet ) para verificar anagramas en las cadenas procesadas:
String preprocess(String source) { return source.replaceAll("[^a-zA-Z]", "").toLowerCase(); } boolean isLetterBasedAnagramMultiset(String string1, String string2) { return isAnagramMultiset(preprocess(string1), preprocess(string2)); }Este enfoque puede ser una forma general de resolver todas las variantes de los problemas de anagramas. Por ejemplo, si también queremos incluir dígitos, solo necesitamos ajustar el filtro de preprocesamiento.
7. Conclusión
En este artículo, analizamos tres algoritmos para verificar si una cadena dada es un anagrama de otra, carácter por carácter. Para cada solución, discutimos las compensaciones entre la velocidad, la legibilidad y el tamaño de la memoria requerida.
También vimos cómo adaptar los algoritmos para buscar anagramas en el sentido lingüístico más tradicional. Logramos esto procesando previamente las entradas en letras minúsculas.
Como siempre, el código fuente del artículo está disponible en GitHub.