Was ist der beste Weg, dies zu lösen:
Ich habe eine Gruppe von Arrays mit 3-4 Zeichen innerhalb jedes wie folgt:
%Vor%Ich habe auch eine Reihe von Wörterbuchwörtern.
Was ist der beste / schnellste Weg, um herauszufinden, ob sich das Array von Zeichen zu einem der Wörterbuchwörter kombinieren lässt? Zum Beispiel könnten die obigen Arrays die Wörter machen:
"pat", "rat", "at", "zu", "bum" (lol)
aber nicht "nub" oder "mat"
Sollte ich durch das Wörterbuch gehen, um Wörter zu sehen kann gemacht werden oder alle Kombinationen aus den Buchstaben erhalten dann vergleichen Sie diese mit dem Wörterbuch
Ich hatte etwas Scrabble-Code herumliegen, also konnte ich das zusammenwerfen. Das Wörterbuch, das ich benutzte, ist sowpods (267751 Wörter). Der folgende Code liest das Wörterbuch als eine Textdatei mit einem Großbuchstaben in jeder Zeile.
Der Code ist C #:
%Vor%Hier ist die Ausgabe, wenn Sie Ihre Testdaten verwenden:
%Vor%Und die Ausgabe bei zufälligen Daten (druckt nicht jedes Wort):
%Vor%BEARBEITEN: Ich habe es mit zwei Änderungen viel schneller gemacht: Das Wort an jedem Endknoten des Trie speichern, so dass es nicht neu aufgebaut werden muss. Und Speichern der Eingabebuchstaben als ein Array von Hash-Sätzen anstelle eines Arrays von Arrays, so dass der Aufruf Contains () schnell ist.
Es gibt wahrscheinlich viele Möglichkeiten, dies zu lösen.
Was Sie interessiert, ist die Nummer jedes Zeichens , das Sie zum Bilden eines Wortes zur Verfügung haben, und wie viele Zeichen jedes Zeichens für jedes Wörterbuch benötigt werden. Der Trick besteht darin, diese Informationen effizient im Wörterbuch nachzuschlagen.
Vielleicht können Sie einen Präfix-Baum ( ein Trie ), eine Art Smart-Hash-Tabelle oder ähnliches verwenden.
Wie auch immer, Sie werden wahrscheinlich alle Ihre Möglichkeiten ausprobieren und sie mit dem Wörterbuch vergleichen müssen. Das heißt, wenn Sie drei Felder mit jeweils drei Werten haben, gibt es 3 ^ 3 + 3 ^ 2 + 3 ^ 1 = 39 Kombinationen zum Auschecken. Wenn dieser Prozess zu langsam ist, könnten Sie vielleicht einen Bloom-Filter vor das Wörterbuch stellen, um schnell zu überprüfen, ob a Wort ist definitiv nicht im Wörterbuch.
BEARBEITEN: Wie auch immer, ist das nicht im Wesentlichen dasselbe wie Scrabble? Vielleicht googeln Sie für den Scrabble-Algorithmus "gibt Ihnen einige gute Hinweise.
Die umformulierte Frage kann nur durch Generieren und Testen beantwortet werden. Da Sie 4 Buchstaben und 10 Felder haben, haben Sie nur 1 Million mögliche Kombinationen (10 Millionen, wenn Sie ein Leerzeichen zulassen). Sie benötigen eine effiziente Möglichkeit, sie zu suchen, einen BDB oder eine Art von Festplatten-Hash zu verwenden.
Die zuvor gepostete Trie-Lösung sollte ebenfalls funktionieren. Sie sind nur noch mehr darauf beschränkt, welche Zeichen Sie in jedem Schritt der Suche auswählen können. Es sollte auch schneller sein.
Tags und Links algorithm dictionary