Javascript: Überprüfen Sie, ob der String durch die Kombination anderer Strings in einem Array neu erstellt werden kann.

Question

Javascript: Überprüfen Sie, ob der String durch die Kombination anderer Strings in einem Array neu erstellt werden kann.

8

Ich versuche herauszufinden, wie man am besten prüft, ob eine bestimmte Zeichenkette durch Kombinieren anderer Zeichenketten, die ich in einem Array habe, erzeugt werden kann. Die anderen Zeichenfolgen können eine beliebige Länge einschließlich eines Zeichens haben. Außerdem können die Zeichen in den anderen Zeichenfolgen neu angeordnet werden.

Wenn wir also nach dem Wort "dodge" suchen würden und unser String-Array ['god','house','d','e','cat','c','r','jump'] wäre, hätten wir eine Übereinstimmung, da wir die Buchstaben in "god", "d" und "e" kombinieren könnten Erstelle 'Ausweichen'.

Wenn das Array "dot" anstelle von "d" enthält, hätten wir keine Übereinstimmung, da wir alle Zeichen in jedem der Wörter, die wir rekombinieren, verwenden müssen (wir müssten 'o' und ' t 'genauso gut.

Ich möchte auch wissen, welche Wörter verwendet wurden, um das angegebene Wort zu erstellen. Wenn es also eine Übereinstimmung gibt, möchte ich, dass die Funktion die Array-Indizes der Wörter zurückgibt, die neu kombiniert wurden, um das angegebene Wort zu erstellen. Für das obige "Ausweichen" Beispiel würde es [0,2,3] zurückgeben.

javascript

makeee 21.03.2011, 01:59

quelle

5 Antworten

1

BEARBEITEN
Dies sollte viel schneller als die naive Lösung sein, da die ganze Arbeit von der eingebauten indexOf-Suche gemacht wird, die wirklich schnell ist, und sie kann bei der ersten Nichtübereinstimmung beendet werden.

%Vor%

Dies ist die naive Lösung:

%Vor%

Es sollte Optimierungen geben, die gemacht werden können, um es schneller zu machen, wenn das ein Problem ist.

Amjad Masad 21.03.2011 02:29

quelle

1

Algorithmus:

Brechen Sie die Zielzeichenfolge in Buchstaben und gruppieren Sie sie, erhalten Sie die Anzahl der einzelnen Buchstaben
Bilden Sie alle Permutationen von Strings im Array, beginnend mit 1 String und bis zum gesamten Array. Wenn Ihr Zeichenfolgenarray kurz ist (d. H. & Lt; 32), können Sie eine Ganzzahl mit automatischer Inkrementierung mit Bitmaske erstellen, um alle Permutationen zu generieren. Wenn Ihr String-Array lang ist (& gt; 32), dann verwenden Sie ein Array, um jeden "Bit" -Slot mit einer String-Länge zu speichern und eine inkrementierende Ganzzahl zu simulieren.
Überspringe alle Permutationen, die nicht die gleiche Länge wie die Zielzeichenfolge haben (dies sollte 90% aller Permutationen eliminieren). Erhalten Sie die Gesamtzahl der Buchstaben, indem Sie die Anzahl der "1" Bits x Länge der Zeichenfolge (oder Summierungsschlitze) addieren; Es muss = Ziel String Länge.
Zerlegen Sie für jede Permutation die Buchstaben und gruppieren Sie sie, um jeden Buchstaben zu zählen
Durchlaufen Sie die Zielzeichenfolgengruppe Buchstabe für Buchstabe und vergleichen Sie die Anzahl mit der Gruppe der Zeichenfolge. Die Buchstaben und Zählungen müssen genau gleich sein, um erfolgreich zu sein. Wenn ja, gib diese Permutation als Antwort zurück.
Ansonsten fahren Sie mit einer anderen Permutation fort
Wenn Sie alle Permutationen durchgelaufen haben, geben Sie fail zurück.

Eine JavaScript-Implementierung:

%Vor%

Vorbehalt: Ich habe nicht versucht, das auszuführen. Lass es mich wissen, wenn ich hier oder da einen Tippfehler gemacht habe.

Stephen Chung 21.03.2011 02:29

quelle

0

Siehe Beispiel hier →

%Vor%

mVChr 21.03.2011 03:19

quelle

0

Ich habe gerade festgestellt, dass dieses Problem mit dem Problem mit der Untermenge von Produkten vergleichbar ist. und daher NP-Complete.

Lassen Sie s(x) eine Größenmethode sein, die eine ganze Zahl für jeden String zurückgibt, indem Sie die Zeichen auf Primzahlen abbilden und dann das Produkt dieser Primzahlen zurückgeben:

%Vor%

Dann bekommen wir

%Vor%

Bei einem gegebenen Dictionary A suchen wir nun nach einer Untermenge A'⊂ A , so dass das Produkt

ist %Vor%

entspricht s(key) für eine gegebene key .

Elian Ebbing 21.03.2011 07:46

quelle

Tags und Links javascript

Django: Verwenden von Annotate, Count und Distinct in einem Queryset MongoDB, C # und NoRM + Denormalisierung

score 3 · Accepted Answer

Ich habe eine Lösung geschrieben, die den schlimmsten Fall O(2^n) hat, aber sie wird in den meisten Situationen ziemlich gut funktionieren. Ich habe mit einer Funktion begonnen, die jeden String einem Objekt zuordnet, das alle Buchstaben des Strings zählt. Beispiel:

%Vor%

Wie Sie sehen können, speichert es auch die Größe im Ergebnis. Dies ist die Implementierung:

%Vor%

Dann schreibe ich eine Funktion, die zwei gemappte Objekte "subtrahiert". Zum Beispiel:

%Vor%

Wie Sie im letzten Beispiel sehen können, gibt die Funktion null zurück, wenn die Subtraktion nicht möglich ist. Dies ist eine Implementierung für subtract :

%Vor%

Der letzte Schritt ist das Schreiben einer Methode findCombination(word, dict) , die eine Kombination zurückgibt, wenn sie eine oder null findet. Beispiele:

%Vor%

Ich verwende eine rekursive Methode mit Backtracking, wobei ich versuche, Wörter von dem gegebenen Schlüssel zu "subtrahieren", bis das Ergebnis "leer" ist:

%Vor%

Sie könnten (und sollten) den Code optimieren, indem Sie die Variable mappedDict nur einmal initialisieren, und nicht jedes Mal, wenn findCombination() aufgerufen wird.