Aufeinanderfolgendes Hinzufügen von char, um das längste Wort im Wörterbuch zu erhalten [geschlossen]

Der Brute-Force-Ansatz würde versuchen, Buchstaben zu jedem verfügbaren Index hinzuzufügen, indem eine Tiefensuche verwendet wird.

Also, beginnend mit "a", gibt es zwei Stellen, an denen Sie einen neuen Buchstaben hinzufügen können. Vor oder hinter dem 'a', dargestellt durch Punkte darunter.

.a.

Wenn Sie ein 't' hinzufügen, gibt es jetzt drei Positionen.

.a.t.

Sie können versuchen, alle 26 Buchstaben zu jeder verfügbaren Position hinzuzufügen. Das Wörterbuch kann in diesem Fall eine einfache Hashtabelle sein. Wenn Sie ein 'z' in der Mitte hinzufügen, erhalten Sie 'azt', das nicht in der Hashtabelle wäre, so dass Sie diesen Pfad in der Suche nicht fortsetzen.

Bearbeiten : Nick Johnsons Grafik hat mich neugierig gemacht, wie ein Graph aller maximalen Pfade aussehen würde. Es ist ein großes (1,6 MB) Bild hier:

Ссылка

Bearbeiten : Hier ist eine Python-Implementierung. Der Brute-Force-Ansatz läuft tatsächlich in einer angemessenen Zeit (einige Sekunden, abhängig vom Anfangsbuchstaben).

Natürlich wird es eine Menge Verbindungen in der Antwort geben. Dadurch werden die oberen N Ergebnisse gedruckt, gemessen anhand der Länge des letzten Wortes.

Ausgabe für den Anfangsbuchstaben 'a' mit dem TWL06 Scrabble Wörterbuch.

Und hier sind die Ergebnisse für jeden Anfangsbrief. Natürlich wird eine Ausnahme gemacht, dass der einzelne Anfangsbuchstabe nicht im Wörterbuch sein muss. Nur ein 2-Buchstaben-Wort, das damit gebildet werden kann.

Wenn Sie das einmal machen wollen, würde ich Folgendes tun (generalisiert auf das Problem, mit einem ganzen Wort zu beginnen):

Nehmen Sie Ihr gesamtes Wörterbuch und werfen Sie alles weg, das keine Übermenge der Zeichen in Ihrem Zielwort hat (sagen wir, es hat die Länge m ). Dann binde die restlichen Wörter nach Länge. Versuchen Sie für jedes Wort der Länge m+1 , jeden Buchstaben fallen zu lassen und sehen Sie, ob das Ihr gewünschtes Wort ergibt. Wenn nicht, werfen Sie es. Dann überprüfe jedes Wort der Länge m+2 mit dem gültigen Satz der Länge m+1 und lasse alle Wörter fallen, die nicht reduziert werden können. Mach weiter bis du ein leeres Set findest; das letzte, was du gefunden hast, wird am längsten sein.

Wenn Sie so schnell nachschlagen möchten, würde ich eine Suffix-Baum- wie Datenstruktur erstellen.

Gruppiere alle Wörter nach Länge. Platziere für jedes Wort der Länge 2 jedes seiner zwei Zeichen in einem "Unterwort" -Satz und füge dieses Wort zu jedem der "Superword" -Sätze des Zeichens hinzu. Jetzt haben Sie eine Verbindung zwischen allen gültigen Wörtern der Länge 2 und allen Zeichen. Machen Sie dasselbe mit Wörtern der Länge 3 und gültigen Wörtern der Länge 2. Jetzt können Sie irgendwo in dieser Hierarchie beginnen und eine Breitensuche durchführen, um den tiefsten Zweig zu finden.

Edit: Die Geschwindigkeit dieser Lösung hängt stark von der Struktur der Sprache ab, aber wenn wir uns entscheiden, alles mit Sets mit log(n) Performance für alle Operationen zu erstellen (dh wir verwenden rot-schwarze Bäume oder ähnliches), und wir haben N(m) words der Länge m , um dann die Verbindung zwischen Wörtern der Länge m+1 und m wird ungefähr (m+1)*m*N(m+1)*log(N(m)) Zeit (unter Berücksichtigung, dass String vergleicht lineare Zeit in der Länge der Zeichenfolge). Da wir dies für alle Wortlängen tun müssen, wird die Laufzeit für das Erstellen der vollständigen Datenstruktur etwas in der Größenordnung von

(Das anfängliche Binning in Wörter einer bestimmten Länge dauert linear, daher kann es vernachlässigt werden; die tatsächliche Formel für die Laufzeit ist kompliziert, weil sie von der Verteilung der Wortlängen abhängt; für den Fall, dass Sie es von a machen einzelnes Wort ist es noch komplizierter, weil es von der erwarteten Anzahl von längeren Wörtern abhängt, die kürzere Unterwörter haben.)

Angenommen, Sie müssen dies wiederholt tun (oder Sie wollen die Antwort für jeden der 26 Buchstaben), tun Sie es rückwärts:

1. Laden Sie ein Wörterbuch und sortieren Sie es nach Länge, absteigend
2. Erstellen Sie ein zunächst leeres Mapping zwischen Wörtern und (extension, max_len) Tupeln.
3. Für jedes Wort in der sortierten Liste:
   1. Wenn es bereits im Mapping ist, rufen Sie die maximale Länge ab.
   2. Wenn nicht, setze die maximale Länge auf die Wortlänge.
   3. Untersuche jedes Wort, das durch Löschen eines Zeichens erzeugt wurde. Wenn dieses Wort nicht im Mapping enthalten ist oder unser max_len das max_len des bereits im Mapping vorhandenen Worts überschreitet, aktualisieren Sie das Mapping mit dem aktuellen Wort und max_len

Dann, um die Kette für ein gegebenes Präfix zu erhalten, beginnen Sie einfach mit diesem Präfix und suchen Sie es und seine Erweiterungen wiederholt im Wörterbuch nach.

Hier ist der Beispiel-Python-Code:

Und seine Ausgabe für jeden Buchstaben des Alphabets:

Edit: Angesichts des Ausmaßes, zu dem Zweige gegen Ende zusammenlaufen, dachte ich, es wäre interessant, eine Grafik zu zeichnen, um dies zu demonstrieren:

Eine interessante Erweiterung dieser Herausforderung: Es ist wahrscheinlich, dass es für einige Buchstaben mehrere gleich lange abschließende Wörter gibt. Welcher Satz von Ketten minimiert die Anzahl der Endknoten (zB fusioniert die meisten Buchstaben)?