Hvis to ord eller sætninger er anagrammer , de deler nøjagtig samme sæt af bogstaver i en anden rækkefølge . For eksempel, " lytte " og " tavse " er anagrammer . Du kan oprette en algoritme med orden n log ( n ) effektivitet, der kontrollerer, om en liste over givne ord er anagrammer . Sortere derefter med en O (n log ( n ) ) sorteringsmetode og bruge en hash tabel til at sammenligne resultaterne. Instruktioner
1
Opret en hash tabel, der har en nøgle og en liste over værdier , der er forbundet med hver tast. Begyndende med det første ord , gentage gennem listen over ord
2
Sorter bogstaverne i ordet ved hjælp fusionere sortere, heap sortere, binært træ slags eller en tilsvarende slags, der kører som O (n log. ( n ) ) . Husk, at anagrammer er identiske , når sorteres.
3
Slå op i sorteres ord i hash tabellen. Tilsæt usorteret ord til de værdier, der er knyttet til hash nøgle, hvis tasten allerede eksisterer. Tilsæt sorteres ord som et nyt hash nøgle og usorteret ord som en værdi knyttet til hash nøglen, hvis hash nøgle ikke eksisterer. For eksempel givet " rotte ", " tar " og " kunst" add "kunst " som hash nøgle og " rotte " som en værdi , tilføje " tjære " som en værdi " er knyttet til "kunst" , og tilføj "kunst" som en værdi knyttet til "kunst ".
4
Fortsæt med hvert ord i listen . Når du når til slutningen af listen , udskrive hver hash nøgle og dens tilhørende værdier for at få vist de fundne anagrammer .
5.
Tæl sammenligninger til at validere, at den slags sker i " O (n log (n ) ) " , og at sammenligningen sker i O ( 1).