Dado un conjunto de cadenas, devuelva todos los grupos de cadenas que son anagramas

Question

Dado un conjunto de cadenas, devuelva todos los grupos de cadenas que son anagramas.

Mis soluciones:

Para cada palabra cadena de la matriz, una especie que O (m lg m), m es la longitud media de una palabra.

Crear un hash Tabla < cadena, lista>.

Poner la palabra ordenada en la tabla hash como clave y también generar todas las permutaciones (O (m!)) De la palabra, buscar cada permutación en un diccionario (un mapa de árbol de prefijos) con O (m), si está en el diccionario, colóquelo (O (1)) en la tabla hash para que todas las palabras permutadas se incluyan en la lista con la misma clave.

Totalmente, O (n * m * lg m * m!) Tiempo y O (n * m!) Espacio, n es el tamaño de la matriz dada.

Si m es muy grande, no es eficiente, m! .

¿Alguna mejor solución?

gracias

Answer 1

utilizar el conteo Clasificar para clasificar la voz para que la clasificación se puede hacer en O (m). después de ordenar generar llave de palabra e insertar un nodo (clave, valor) en hashtable. La clave generadora se puede lograr en O (m).

Puede tomar el valor en (clave, valor) como una matriz dinámica que puede contener más de una cadena. Cada vez que inserta una clave que ya está presente simplemente presione la palabra original desde la cual se genera la clave en la matriz de valores.

Así que la complejidad general del tiempo O (mn) donde n es el número total de palabras (tamaño de la entrada).

También este enlace tiene solución a problemas-similares> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42

Answer 2

Definimos un alfabeto, que contiene todas las cartas que podamos tener en nuestra lista de palabras. A continuación, necesitamos un primado diferente para cada una de las letras en el alfabeto, le recomiendo usar el más pequeño que pueda encontrar.

Eso nos daría la siguiente asignación: {a => 2, b => 3, c => 5, d => 7, etc}

Ahora cuente las letras de la palabra que desea representar como un número entero, y construir su número entero resultado como sigue:

Pseudocódigo:

result = 1 
for each letter: 
....result *= power(prime[letter], count(letter,word) 

algunos ejemplos:

AAAA => 2^4

aabb => 2^2 * 3^2 = bbaa = baba = ...

y así sucesivamente.

Por lo tanto, tendrá un número entero que represente cada palabra en su diccionario y la palabra que desea verificar se podrá convertir a un número entero. Entonces, si n es el tamaño de su lista de palabras yk es el tamaño de la palabra más larga, tomará O (nk) para construir su nuevo diccionario y O (k) para verificar una nueva palabra.

Hackthissite.com tiene un desafío de programación que es: Dada una palabra mezclada, búsquela en un diccionario para ver si algún anagrama está en el diccionario. Hay un good article en una solución eficiente al problema del cual he tomado prestada la respuesta, también entra en detalles sobre otras optimizaciones.

Answer 3

#include <map> 
#include <iostream> 
#include <set> 
#include <algorithm> 

int main() { 
    std::string word; 
    std::map<std::string, std::set<std::string>> anagrams; 
    while(std::cin >> word) { 
    std::string sortedWord(word); 
    std::sort(sortedWord.begin(), sortedWord.end()); 
    anagrams[sortedWord].insert(word); 
    } 
    for(auto& pair : anagrams) { 
    for(auto& word : pair.second) { 
     std::cout << word << " "; 
    } 
    std::cout << "\n"; 
    } 
} 

Voy a dejar que alguien que es mejor en el análisis de gran O que me imagino las complejidades.

Answer 4

convierta el diccionario en un mapeo de los caracteres ordenados de una palabra asignada a cada palabra de esos caracteres y almacénelo. Para cada palabra que le den, ordénela y agregue la lista de anagramas de la asignación a su salida.

Answer 5

No creo que se puede hacer mejor en términos de S

• clasificación de las letras de cada palabra
• clasificación de la lista de palabras ordenadas
• cada conjunto de anagramas ahora se agruparán de forma consecutiva .