Wörter in einem Wörterbuch mit einem Wort kombinieren

Question

Ich arbeite an einem Problem, bei dem ich prüfen muss, wie viele Wörter in einem Wörterbuch kombiniert werden können, um ein einzelnes Wort zu finden.

Zum Beispiel:
die Zeichenfolge gegeben "hellogoodsir", und das Wörterbuch: {Hallo, gut, Sir, gehen, od, e, l}, ist das Ziel, alle möglichen Kombinationen zu finden, Form die Schnur.

In diesem Fall würde das Ergebnis hallo + gut + Sir und hallo sein + go + od + Sir, in resultierenden 3 + 4 = 7 Worten verwendet, oder 1 + 1 = 2 Kombinationen.

Was ich habe, ist einfach, alle Wörter beginnend mit dem ersten Zeichen ("h" in diesem Fall) in einem hashmap (startH) und den Rest in einem anderen hashmap (endH). Ich gehe dann jedes einzelne Wort im startH hashmap durch und überprüfe, ob "hellogoodsir" das neue Wort (start + end) enthält, wobei end jedes Wort im endH hashmap ist. Wenn dies der Fall ist, prüfe ich, ob es mit dem passenden Wort übereinstimmt, und inkrementiere dann den Zähler mit dem Wert der Zahl für jedes verwendete Wort. Wenn es es enthält, aber nicht gleich ist, rufe ich dieselbe Methode (Rekursion) unter Verwendung des neuen Wortes (dh start + end) auf und versuche, irgendein Wort am Ende hashmap an das neue Wort anzuhängen, um a zu erhalten Spiel.

Dies ist offensichtlich sehr langsam für eine große Anzahl von Wörtern (und eine lange Zeichenfolge zu entsprechen). Gibt es einen effizienteren Weg, um dieses Problem zu lösen?
Soweit ich weiß, ist dies ein O (n^2) Algorithmus, aber ich bin mir sicher, dass dies schneller erledigt werden kann.

Answer 1

Beginnen wir mit Ihrer Lösung. Es ist keine lineare oder quadratische Zeit, sondern eine exponentielle Zeit. Ein Gegenbeispiel, das zeigt, dass ist:

word = "aaa...a" 
dictionary = {"a", "aa", "aaa", ..., "aa...a"} 

Da Ihre Lösung durch jede mögliche Übereinstimmung wird, und es gibt exponentielle Anzahl solcher in diesem Beispiel - die Lösung exponentielle Zeit.

D[0] = 1 # 
D[i] = sum { D[j] | word.Substring(i,j) is in the dictionary | 0 <= j < i } 

jeder D[i] Berechnung (die vorherigen gegeben sind bereits bekannt) erfolgt in:

können jedoch, dass effizient (quadric Zeit worst case), mit Dynamic Programming, die rekursive Formel durch folgende getan mehr werden O(i) Dies ergibt insgesamt O(n^2) Zeit, mit O(n) zusätzlichen Speicherplatz.

Schnell Note: Mit dem für jeden D[i] das Wörterbuch anstelle aller (i,j) Paare laufen, können Sie O (k) Zeit für jeden D [i], erreichen die als O(n*k) endet, wo k ist die Größe des Wörterbuchs. Dies kann in einigen Fällen optimiert werden, indem nur potentiell gültige Strings durchlaufen werden, aber für das gleiche Zählerbeispiel wie oben wird es O(n*k) ergeben.

Beispiel:

dictionary = {hello, good, sir, go, od, e, l} 
string = "hellogoodsir" 
D[0] = 1 
D[1] = 0 (no substring h) 
D[2] = 0 (no substring he, d[1] = 0 for e) 
... 
D[5] = 1 (hello is the only valid string in dictionary) 
D[6] = 0 (no dictionary string ending with g) 
D[7] = D[5], because string.substring(5,7)="go" is in dictionary 
D[8] = 0, no substring ending with "oo" 
D[9] = 2: D[7] for "od", and D[5] for "good" 
D[10] = D[11] = 0 (no strings in dictionary ending with "si" or "s") 
D[12] = D[7] = 2 for substring "sir" 

Answer 2

würde Mein Vorschlag eine prefix tree zu bedienen.Die Knoten unterhalb der Wurzel wären h, g, s, o, e und l. Sie benötigen auch Knoten zum Beenden von Zeichen, um zwischen go und good zu unterscheiden.

Um nach allen Übereinstimmungen zu suchen, verwenden Sie einen Breadth-First-Search-Ansatz. Der Status, den Sie im Auge behalten möchten, ist eine Zusammensetzung aus: dem aktuellen Index in der Suchzeichenfolge, dem aktuellen Knoten in der Struktur und der Liste der bisher verwendeten Wörter.

Der Ausgangszustand sollte 0, Wurzel, []

sein Während die Liste der Staaten ist dequeue der nächste Zustand nicht leer ist, und sehen, ob der Index eine der Tasten der Kinder des Knotens übereinstimmt. Wenn dies der Fall ist, ändern Sie eine Kopie des Status und fügen Sie ihn in die Warteschlange ein. Wenn eines der untergeordneten Zeichen das abschließende Zeichen ist, führen Sie das gleiche aus und fügen Sie das Wort der Liste im Status hinzu.

Ich bin nicht sicher auf der O (n) Zeit auf diesem Algorithmus, aber es sollte viel schneller sein.