Dies ist eine Interviewfrage (Telefonbildschirm): Schreibe eine Funktion (in Java), um alle Permutationen eines gegebenen Wortes zu finden, die in einem gegebenen Text vorkommen. Zum Beispiel sollte für abc und text abcxyaxbcayxycab die Funktion abc, bca, cab zurückgeben.
Ich würde diese Frage wie folgt beantworten:
Offensichtlich kann ich alle Permutationen des gegebenen Wortes durchlaufen und eine Standardfunktion substring verwenden. Es könnte jedoch schwierig sein (für mich gerade), Code zu schreiben, um alle Wortpermutationen zu generieren.
Es ist einfacher, alle Text-Teilstrings der Wortgröße zu durchlaufen, jeden Teilstring zu sortieren und ihn mit dem "sortierten" gegebenen Wort zu vergleichen. Ich kann eine solche Funktion sofort programmieren.
Ich kann wahrscheinlich einen Teilstringsuchalgorithmus modifizieren, aber ich erinnere mich nicht mehr an diese Algorithmen.
Wie würden Sie diese Frage beantworten?
Dies ist wahrscheinlich nicht die effizienteste Lösung algorithmisch, aber es ist sauber aus Sicht des Klassenentwurfs. Diese Lösung verwendet den Ansatz, "sortierte" Wörter zu vergleichen.
Wir können sagen, dass ein Wort eine Permutation eines anderen ist, wenn es die gleichen Buchstaben in der gleichen Zahl enthält. Das bedeutet, dass Sie das Wort von einem String in ein Map<Character,Integer> umwandeln können. Eine solche Konvertierung wird eine Komplexität O (n) haben, wobei n die Länge von String ist, vorausgesetzt, dass Einfügungen in Ihrer Map Implementierung O (1) kosten.
Das Map enthält als Schlüssel alle im Wort gefundenen Zeichen und als Werte die Häufigkeit der Zeichen.
Beispiel abbc wird in [a->1, b->2, c->1]
bacb wird in [a->1, b->2, c->1]
Wenn Sie also wissen müssen, ob zwei Wörter die eine Permutation der anderen sind, können Sie beide in Maps konvertieren und dann Map.equals aufrufen.
Dann müssen Sie über die Textzeichenfolge iterieren und die Transformation auf alle Unterstrings derselben Länge der Wörter anwenden, die Sie suchen.
Von Inertial vorgeschlagene Verbesserung
Dieser Ansatz kann verbessert werden, indem die Map "rollend" aktualisiert wird.
i.e. Wenn Sie im Beispiel-Heuschober im OP (Teilstring i=3 ) zum Index xya passen, ist die Karte [a->1, x->1, y->1] . Wenn Sie im Heuhaufen vorrücken, verringern Sie die Anzahl der Zeichen für haystack[i] und erhöhen Sie die Anzahl für haystack[i+needle.length()] .
(Löschen von Nullen, um sicherzustellen, dass Map.equals() funktioniert, oder einfach einen benutzerdefinierten Vergleich implementieren.)
Von Max vorgeschlagene Verbesserung
Was ist, wenn wir auch matchedCharactersCnt variable einführen? Zu Beginn des Heuhaufens wird es 0 sein. Jedes Mal, wenn Sie Ihre Karte in Richtung des gewünschten Werts ändern, erhöhen Sie die Variable. Jedes Mal, wenn Sie den gewünschten Wert ändern, dekrementieren Sie die Variable. Bei jeder Iteration prüfen Sie, ob die Variable der Länge der Nadel entspricht. Wenn es ist - Sie haben eine Übereinstimmung gefunden. Es wäre schneller als jedes Mal die komplette Karte zu vergleichen.
Von Max bereitgestellter Pseudocode:
%Vor%Um eine Permutation einer Zeichenkette zu finden, können Sie die Zahlentheorie verwenden. Aber Sie müssen die "Theorie" hinter diesem Algorithmus im Voraus kennen, bevor Sie die Frage mit diesem Algorithmus beantworten können.
Es gibt eine Methode, mit der Sie einen Hash eines Strings mit Primzahlen berechnen können. Jede Permutation derselben Zeichenfolge ergibt den gleichen Hash-Wert. Alle anderen String-Kombinationen, die keine Permutation sind, ergeben einen anderen Hash-Wert.
Der Hash-Wert wird berechnet durch c 1 p 1 + c 2 p 2 + ... + c n
Hier ist die Implementierung.
%Vor%Die Ausgabe von diesem ist: ABC bca Taxi
Der zweite Ansatz erscheint mir sehr elegant und sollte vollkommen akzeptabel sein. Ich denke es skaliert bei %code% , wobei %code% Wortlänge und %code% Textlänge ist.
Ich kann einen etwas komplexeren %code% Algorithmus entwickeln:
BEARBEITEN : Sehen Sie, dass mehrere ähnliche Antworten gepostet wurden. Der größte Teil dieses Algorithmus entspricht der von anderen vorgeschlagenen Rollfrequenzzählung. Meine bescheidene Ergänzung aktualisiert auch die Anzahl der Unterschiede in einer rollenden Art und Weise, was einen %code% -Algorithmus ergibt und nicht %code% one.
EDIT2 : Habe gerade gesehen, dass Max das in den Kommentaren grundsätzlich vorgeschlagen hat, also zeigt Brownie auf ihn.
Dieser Code sollte die Arbeit machen:
%Vor%Die CharsActuallyFound-Liste wird verwendet, um den Charakter zu verfolgen, der bereits in der Schleife gefunden wurde. Es ist notwendig, mathing "aaa" "bbb" "ccc" (hinzugefügt von mir zu dem von Ihnen angegebenen Text) zu vermeiden.
Nach weiterem Nachdenken denke ich, dass mein Code nur funktioniert, wenn das gegebene Wort keine doppelten Zeichen hat. Der obige Code druckt korrekt
%Vor%Wenn Sie jedoch nach dem Wort "aaa" suchen, wird nichts gedruckt, da jedes Zeichen nicht mehr als einmal gefunden werden kann. Inspiriert von Jim Mischels Antwort, bearbeite ich meinen Code und beende damit:
%Vor%Dies gibt mir folgende Ausgabe:
%Vor%Hat ein Benchmark, fand der Code oben 30815 Übereinstimmungen von "abc" in einer zufälligen Zeichenfolge von 36M in nur 4,5 Sekunden. Wie Jim bereits sagte, danke für dieses Puzzle ...
Das würde ich tun - richte ein Flag-Array mit einem ein Element gleich 0 oder 1, um anzugeben, ob dieses Zeichen in STR war abgestimmt worden
Setzen Sie die erste Ergebniszeichenfolge RESULT auf leer.
für jedes Zeichen C in TEXT:
Setzen Sie ein Array X gleich der Länge von STR auf alle Nullen.
für jedes Zeichen S in STR: Wenn C das JTH-Zeichen in STR ist und X [J] == 0, dann setze X [J] & lt; = 1 und füge hinzu C zu ERGEBNIS. Wenn die Länge von RESULT gleich STR ist, Fügen Sie RESULT zu einer Liste von Permutationen hinzu und setze die Elemente von X [] wieder auf Nullen.
Wenn C kein Zeichen J in STR mit X [J] == 0 ist, Setzen Sie dann die Elemente von X [] wieder auf Nullen.
Sie sollten dies in einem einzigen Durchgang tun können. Beginnen Sie mit dem Erstellen einer Karte, die alle Zeichen des gesuchten Wortes enthält. Zu Beginn enthält die Karte also %code% .
Durchlaufen Sie nun den Text um jeweils ein Zeichen. Die Schleife sieht in Pseudocode etwa so aus.
%Vor%Wenn Sie eindeutige Vorkommen möchten, ändern Sie den Ausgabeschritt so, dass er die gefundenen Zeichenfolgen zu einer Karte hinzufügt. Das wird Dubletten eliminieren.
Es gibt Wörter, die doppelte Buchstaben enthalten. Wenn das ein Problem ist, den Schlüssel den Buchstaben und den Wert eine Zählung bilden. 'Entfernen' eines Zeichens bedeutet das Verringern der Anzahl in der Karte. Wenn der Zähler auf 0 geht, wird das Zeichen tatsächlich aus der Karte entfernt.
Der beschriebene Algorithmus findet keine überlappenden Vorkommen. Mit dem Text %code% wird nur %code% gefunden. Wenn Sie überlappende Vorkommen behandeln möchten, können Sie den Algorithmus so ändern, dass er bei einer Übereinstimmung den Index um eins minus die Länge der gefundenen Zeichenfolge dekrementiert.
Das war ein lustiges Puzzle. Danke.
Dies ist eine Interviewfrage (Telefonbildschirm): Schreibe eine Funktion (in Java), um alle Permutationen eines gegebenen Wortes zu finden, die in einem gegebenen Text vorkommen. Zum Beispiel sollte für %code% und text %code% die Funktion %code% zurückgeben.
Ich würde diese Frage wie folgt beantworten:
Offensichtlich kann ich alle Permutationen des gegebenen Wortes durchlaufen und eine Standardfunktion %code% verwenden. Es könnte jedoch schwierig sein (für mich gerade), Code zu schreiben, um alle Wortpermutationen zu generieren.
Es ist einfacher, alle Text-Teilstrings der Wortgröße zu durchlaufen, jeden Teilstring zu sortieren und ihn mit dem "sortierten" gegebenen Wort zu vergleichen. Ich kann eine solche Funktion sofort programmieren.
Ich kann wahrscheinlich einen Teilstringsuchalgorithmus modifizieren, aber ich erinnere mich nicht mehr an diese Algorithmen.
Wie würden Sie diese Frage beantworten?
Um eine Permutation einer Zeichenkette zu finden, können Sie die Zahlentheorie verwenden. Aber Sie müssen die "Theorie" hinter diesem Algorithmus im Voraus kennen, bevor Sie die Frage mit diesem Algorithmus beantworten können.
Es gibt eine Methode, mit der Sie einen Hash eines Strings mit Primzahlen berechnen können. Jede Permutation derselben Zeichenfolge ergibt den gleichen Hash-Wert. Alle anderen String-Kombinationen, die keine Permutation sind, ergeben einen anderen Hash-Wert.
Der Hash-Wert wird berechnet durch c 1 p 1 + c 2 p 2 + ... + c n
Hier ist die Implementierung.
%Vor%Die Ausgabe von diesem ist: ABC bca Taxi
Sie sollten dies in einem einzigen Durchgang tun können. Beginnen Sie mit dem Erstellen einer Karte, die alle Zeichen des gesuchten Wortes enthält. Zu Beginn enthält die Karte also [a, b, c] .
Durchlaufen Sie nun den Text um jeweils ein Zeichen. Die Schleife sieht in Pseudocode etwa so aus.
%Vor%Wenn Sie eindeutige Vorkommen möchten, ändern Sie den Ausgabeschritt so, dass er die gefundenen Zeichenfolgen zu einer Karte hinzufügt. Das wird Dubletten eliminieren.
Es gibt Wörter, die doppelte Buchstaben enthalten. Wenn das ein Problem ist, den Schlüssel den Buchstaben und den Wert eine Zählung bilden. 'Entfernen' eines Zeichens bedeutet das Verringern der Anzahl in der Karte. Wenn der Zähler auf 0 geht, wird das Zeichen tatsächlich aus der Karte entfernt.
Der beschriebene Algorithmus findet keine überlappenden Vorkommen. Mit dem Text abcba wird nur abc gefunden. Wenn Sie überlappende Vorkommen behandeln möchten, können Sie den Algorithmus so ändern, dass er bei einer Übereinstimmung den Index um eins minus die Länge der gefundenen Zeichenfolge dekrementiert.
Das war ein lustiges Puzzle. Danke.
Das würde ich tun - richte ein Flag-Array mit einem ein Element gleich 0 oder 1, um anzugeben, ob dieses Zeichen in STR war abgestimmt worden
Setzen Sie die erste Ergebniszeichenfolge RESULT auf leer.
für jedes Zeichen C in TEXT:
Setzen Sie ein Array X gleich der Länge von STR auf alle Nullen.
für jedes Zeichen S in STR: Wenn C das JTH-Zeichen in STR ist und X [J] == 0, dann setze X [J] & lt; = 1 und füge hinzu C zu ERGEBNIS. Wenn die Länge von RESULT gleich STR ist, Fügen Sie RESULT zu einer Liste von Permutationen hinzu und setze die Elemente von X [] wieder auf Nullen.
Wenn C kein Zeichen J in STR mit X [J] == 0 ist, Setzen Sie dann die Elemente von X [] wieder auf Nullen.
Der zweite Ansatz erscheint mir sehr elegant und sollte vollkommen akzeptabel sein. Ich denke es skaliert bei O(M * N log N) , wobei N Wortlänge und M Textlänge ist.
Ich kann einen etwas komplexeren O(M) Algorithmus entwickeln:
length(word) ) Zeichen des Textes subFreq
subFreq , was numDiff ergibt.
numDiff gleich Null ist, gibt es eine Übereinstimmung subFreq und numDiff in konstanter Zeit, indem Sie für das erste und übernächste Zeichen im Text BEARBEITEN : Sehen Sie, dass mehrere ähnliche Antworten gepostet wurden. Der größte Teil dieses Algorithmus entspricht der von anderen vorgeschlagenen Rollfrequenzzählung. Meine bescheidene Ergänzung aktualisiert auch die Anzahl der Unterschiede in einer rollenden Art und Weise, was einen O(M+N) -Algorithmus ergibt und nicht O(M*N) one.
EDIT2 : Habe gerade gesehen, dass Max das in den Kommentaren grundsätzlich vorgeschlagen hat, also zeigt Brownie auf ihn.
Dieser Code sollte die Arbeit machen:
%Vor%Die CharsActuallyFound-Liste wird verwendet, um den Charakter zu verfolgen, der bereits in der Schleife gefunden wurde. Es ist notwendig, mathing "aaa" "bbb" "ccc" (hinzugefügt von mir zu dem von Ihnen angegebenen Text) zu vermeiden.
Nach weiterem Nachdenken denke ich, dass mein Code nur funktioniert, wenn das gegebene Wort keine doppelten Zeichen hat. Der obige Code druckt korrekt
%Vor%Wenn Sie jedoch nach dem Wort "aaa" suchen, wird nichts gedruckt, da jedes Zeichen nicht mehr als einmal gefunden werden kann. Inspiriert von Jim Mischels Antwort, bearbeite ich meinen Code und beende damit:
%Vor%Dies gibt mir folgende Ausgabe:
%Vor%Hat ein Benchmark, fand der Code oben 30815 Übereinstimmungen von "abc" in einer zufälligen Zeichenfolge von 36M in nur 4,5 Sekunden. Wie Jim bereits sagte, danke für dieses Puzzle ...