Dato un array di stringhe, restituisce tutti i gruppi di stringhe che sono anagrammi

Question

Dato un array di stringhe, restituisce tutti i gruppi di stringhe che sono anagrammi.

soluzioni My:

Per ogni parola stringa nella matrice, ordinamento è O (m lg m), m è la lunghezza media di una parola.

Compilare una tabella hash < string, lista>.

Inserisci la parola ordinata nella tabella hash come chiave e genera anche tutte le permutazioni (O (m!)) Della parola, cerca ogni permutazione in un dizionario (una mappa albero prefisso) con O (m), se è nel dizionario, metti (O (1)) nella tabella hash in modo che tutte le parole permutate vengano inserite nella lista con la stessa chiave.

Totalmente, O (n * m * lg m * m!) Ora e O (n * m!) Spazio, n è la dimensione della matrice data.

Se m è molto grande, non è efficiente, m! .

Qualche soluzione migliore?

grazie

Answer 1

uso conteggio ordinamento per ordinare la parola in modo che l'ordinamento può essere fatto in O (m). dopo l'ordinamento genera la chiave dalla parola e inserisce un nodo (chiave, valore) nella tabella hash. La chiave di generazione può essere raggiunta in O (m).

È possibile prendere il valore in (chiave, valore) come un array dinamico che può contenere più di una stringa. Ogni volta che si inserisce una chiave già presente, basta premere la parola originale da cui viene generata la chiave sull'array di valori.

Quindi la complessità del tempo complessivo O (mn) dove n è il numero totale di parole (dimensione dell'input).

Anche questo link ha soluzione a problemi-simili> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42

Answer 2

Definiamo un alfabeto, che contiene tutte le lettere che possiamo avere nel nostro vocabolario. Successivamente, abbiamo bisogno di un primo diverso per ciascuna delle lettere dell'alfabeto, ti consiglio di usare il più piccolo che riesci a trovare.

Questo ci darebbe la seguente mappatura: {a => 2, b => 3, c => 5, D => 7, etc}

Ora contano le lettere della parola che si desidera rappresentano come intero, e costruire il vostro intero risultato come segue:

pseudocodice:

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

alcuni esempi:

aaaa => 2^4

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

e così via.

Così avrai un numero intero che rappresenta ogni parola nel tuo dizionario e la parola che vuoi controllare sarà in grado di essere convertita in un numero intero. Quindi se n è la dimensione della tua lista di parole e k è la dimensione della parola più lunga ci vorranno O (nk) per costruire il tuo nuovo dizionario e O (k) per controllare una nuova parola.

Hackthissite.com ha una sfida di programmazione che è: data una parola criptata, cercare in un dizionario per vedere se alcuni anagrammi di esso sono nel dizionario. C'è un good article su una soluzione efficiente al problema da cui ho preso in prestito la risposta, ma entra anche in dettaglio su ulteriori ottimizzazioni.

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

Lascerò a qualcuno che è più bravo in analisi O più grande di quanto non capisca le complessità.

Answer 4

trasforma il dizionario in una mappatura dei caratteri ordinati di una parola mappata a ogni parola di quei caratteri e la memorizza. Per ogni parola che ti è stata data, ordinala e aggiungi l'elenco di anagrammi dalla mappatura al tuo output.

Answer 5

Io non credo che si possa fare meglio in termini di O

• ordinamento delle lettere di ogni parola
• ordinamento dell'elenco di parole ordinate
• ogni serie di anagrammi sarà ora essere raggruppati consecutivamente .