Πώς να γράψετε ένα αλγόριθμο Παραγγελίας N LGN για Έλεγχος Είτε Δύο Δεδομένου λέξεις είναι Anagrams

Αν δύο λέξεις ή φράσεις είναι αναγραμματισμούς , που μοιράζονται την ίδια ακριβώς σειρά επιστολών με διαφορετική σειρά . Για παράδειγμα , "ακούει " και " σιωπηλή " είναι αναγραμματισμούς . Μπορείτε να δημιουργήσετε έναν αλγόριθμο με σκοπό n log (n ) απόδοσης που ελέγχει για να δει εάν η λίστα των λέξεων είναι δεδομένη αναγραμματισμούς . Ταξινόμηση έπειτα με ένα O ( n log (n ) ) μέθοδο ταξινόμησης και να χρησιμοποιήσετε ένα πίνακα κατακερματισμού για να συγκριθούν τα αποτελέσματα . Οδηγίες
Η 1

Δημιουργία ενός πίνακα κατακερματισμού που έχει ένα κλειδί και μια λίστα τιμών που συνδέονται με κάθε πλήκτρο . Αρχίζοντας με την πρώτη λέξη ? Επαναλάβει μέσα από τη λίστα των λέξεων 2

ταξινομήσετε τα γράμματα της λέξης χρησιμοποιώντας συγχώνευση ταξινόμησης , σωρός είδος , δυαδικό δέντρο ταξινόμησης ή συγκρίσιμο είδος που λειτουργεί ως O ( n log . (n)) . Να θυμάστε ότι αναγραμματισμούς είναι πανομοιότυπα όταν ταξινόμηση .
Εικόνων 3

Αναζητήστε την ταξινομημένη λέξη στον πίνακα κατακερματισμού . Προσθέστε το αδιαχώριστα λέξη στις αξίες που συνδέονται με το κλειδί κατακερματισμού , αν υπάρχει ήδη το κλειδί . Προσθέστε την ταξινομημένη λέξη ως ένα νέο κλειδί κατακερματισμού και της αδιαχώριστα λέξη ως αξία για το κλειδί κατακερματισμού , εάν το κλειδί κατακερματισμού δεν υπάρχει . Για παράδειγμα , δίνεται "αρουραίος ", " πίσσα " και " τέχνη ", πρόσθεσε " τέχνη", όπως το κλειδί κατακερματισμού και « αρουραίος » ως τιμή ? Προσθήκη "πίσσα" ως αξία »που επισυνάπτεται στην «τέχνη» και πρόσθεσε «τέχνη» , ως αξία που αποδίδεται στην " τέχνη ".
Η 4

Συνεχίστε με κάθε λέξη στη λίστα . Όταν φτάσετε στο τέλος της λίστας , τυπώστε κάθε δίεση και οι σχετικές τιμές του για να δείτε τις αναγραμματισμούς που βρέθηκαν .
5

Count οι συγκρίσεις γίνονται για να επαληθευτεί ότι το είδος συμβαίνουν στις « O ( n log ( n)) »και ότι η σύγκριση γίνεται σε O ( 1 ) .
Η
εικόνων