Tengo una lista de miles de palabras. ¿Ahora quiero almacenar estas palabras de tal manera que pueda encontrar todos los anagramas para una cadena dada de este diccionario con la mínima complejidad?

Answer 1

Traté de implementar esto usando un HashMap. Aquí está mi algoritmo:
Estoy usando colisión hash para agrupar todos los anagramas. Y usando números primos para evitar colisiones falsas.

1. Crear una matriz de enteros primos
int primos [] = {2, 3, 5, 7, …};
2. Cree un método para obtener el código hash:
int getHashCode (String str) {
int hash = 31;
para (i = 0 a la longitud de str) {
hash = hash * primos [‘a’ – str.charAt [i]];
}
devolver hash;
}
3. Ahora podemos crear un diccionario con todas las palabras dadas:
// Esta tabla hash o mapa se mantendrá, entero como clave y una lista de cadenas como valor.
// Este es un enfoque estándar para implementar el mapa hash. Puede encontrarlo en cualquier API, así que no estoy mencionando sus detalles aquí.
// Puedes buscar en java.util.HashMap
void loadDictionary (String [] palabras) {
para (palabra de palabras; i = 0 a la longitud de las palabras) {
int hash = getHashCode (palabra);
Lista anagrams = dictionary.get (hash);
if (anagramas! = nulo) {
anagrams.add (palabra);
} más
Lista newAnagrams = new ArrayList ();
newAnagrams.add (palabra);
dictionary.put (hash, newAnagrams);
}
}
}
4. Ahora aquí está el enfoque para encontrar anagramas:
int findNumberOfAnagrams (String str) {
Lista anagrams = dictionary.get (getHashCode (str));
return anagrams.size ();
}

Pero siento que podemos implementar de manera más eficiente.

Answer 2

Crea una lista de claves que se generan ordenando las letras de cada palabra. Entonces, para la palabra “perro” la clave sería “dgo” y esa también sería la clave para “dios”. Si las claves de dos palabras son iguales, son anagramas entre sí.