Wie kann ich ein Eingabewort (oder eine Buchstabenfolge) nehmen und ein Wort aus einem Wörterbuch ausgeben, das genau diese Buchstaben enthält?
Hat Java eine englische Wörterbuchklasse (Wortliste), die ich verwenden kann, oder gibt es Open-Source-Implementierungen davon?
Wie kann ich meinen Code optimieren, wenn dies wiederholt durchgeführt werden muss?
Konvertieren Sie Ihr Wörterbuch in ein Anagramm-Wörterbuch . In einem Anagramm-Wörterbuch werden die Wörter in alphabetischer Reihenfolge nach ihren Buchstaben indiziert. Um Anagramme für ein bestimmtes Wort nachzuschlagen, sortieren Sie ihre Buchstaben und suchen entsprechende aus dem Anagramm-Wörterbuch.
Es werden zwei Wörter als Anagramme bezeichnet, wenn sie exakt die gleichen Buchstaben haben, genau die gleiche Anzahl der Zeiten.
Die Überprüfung für Anagramm besteht darin, die Buchstaben beider Wörter zu sortieren und auf Gleichheit zu prüfen:
%Vor% Nun, um alle Anagramme eines gegebenen Wörterbuchworts zu finden, sagen wir word1 , würde ich alle Wörter in dem Wörterbuch finden, für die der obige Test gilt. Um die Suche zu optimieren, können wir einfach nach Wörtern suchen, die gleich lang sind .
Wenn wir dies wiederholt tun müssen, ist es besser, eine Vorverarbeitung durchzuführen. Wir können so etwas wie ein HashMap erstellen, wobei wir ein string einem Set von strings zuordnen würden, die Anagramme sind. Etwas wie:
Nun kann ich jedes Wort in hashMap sehen, um alle seine Anagramme zu erhalten.
Sie können das Anagrams2-Beispiel von der Sun-Site als Startpunkt verwenden Punkt
Um die Leistung zu verbessern, können Sie einen Cache mit Anagrammen für häufig verwendete / kürzlich verwendete Wörter erstellen. Verwenden Sie zu diesem Zweck WeakHashMap
Als unicornaddict erwähnt, können Sie ziemlich einfach feststellen, ob zwei oder nicht Wörter sind Anagramme durch Sortieren, aber das ist ineffizient, besonders wenn Sie es wiederholt tun.
Eine vorbereitete Hash-Tabelle wäre wahrscheinlich die beste Lösung, indem Sie Ihr Wörterbuch zu Beginn des Programms in das Programm laden. Ein ziemlich einfach zu schreibender Algorithmus zum Hashing / Comparing wäre
%Vor%dann
%Vor%Mein Java ist ziemlich rostig, aber ich denke, das würde es tun.
Von meinem POV aus ist der Schlüssel zu dieser Zuweisung, eine Funktion ( hashFunc ) zu finden, die Strings auf Zahlen abbildet, so dass 1) zwei Anagramme auf die gleiche Nummer abgebildet werden, 2) zwei Nicht-Anagramme auf andere abgebildet werden Zahlen. Sobald die Funktion gefunden ist, kann sie einfach auf Eingaben angewendet werden, wodurch langwierige String-Vergleiche vermieden werden:
Hat Java eine englische Wörterbuchklasse (Wortliste), die ich verwenden kann, oder gibt es Open-Source-Implementierungen davon?
Auf Unix-Systemen können Sie mit der Wortdatei
beginnenWie kann ich meinen Code optimieren, wenn dies wiederholt durchgeführt werden muss?
Verwandle das Wörterbuch in eine Hash-Tabelle, indem du hashFunc vorberechnet hast.