Der Brute-Force-Weg kann das Problem in O (n!) lösen und im Grunde alle Permutationen berechnen und die Ergebnisse in einem Wörterbuch überprüfen. Ich suche nach Möglichkeiten, die Komplexität zu verbessern. Ich kann daran denken, einen Baum aus dem Wörterbuch zu bauen, aber immer noch alle Buchstaben-Permutationen zu überprüfen ist O (n!). Gibt es bessere Möglichkeiten, dieses Problem zu lösen?
Buchstaben können Duplikate haben.
Die API für die Funktion sieht so aus:
Nehmen Sie an, dass letters nur Buchstaben von a bis z enthält.
Verwenden Sie ein Ganzzahl-Array, um die Anzahl der Vorkommen eines Zeichens in letters zu zählen.
Überprüfen Sie für jedes Wort im Wörterbuch, ob ein bestimmtes Zeichen in dem Wort mehr als zulässig angezeigt wird. Wenn nicht, fügen Sie dieses Wort in result hinzu.
So können wir sehen, dass die Komplexität der Zeit O (m * k) ist, wobei m die Anzahl der Wörter im Wörterbuch und k die maximale Anzahl der Zeichen in einem Wort ist
Sie können jedes Wort in Ihrem Wörterbuch so sortieren, dass die Buchstaben in der gleichen Reihenfolge wie im Alphabet erscheinen, und dann einen Trie aus Ihren sortierten Wörtern erstellen. (wobei jeder Knoten eine Liste aller Wörter enthält, die aus den Buchstaben gebildet werden können). (lineare Zeit in der gesamten Buchstabenlänge des Wörterbuchs) Sortieren Sie dann die Buchstaben auf die gleiche Weise und gehen Sie durch den Trie mit Tiefensuche zuerst in alle möglichen Richtungen, die eine Teilmenge Ihrer Buchstaben von links nach rechts verwenden. Jedes Mal, wenn Sie einen Knoten im Trie erreichen, der Wörter enthält, geben Sie diese Wörter aus. Jeder Pfad, den Sie untersuchen, kann für mindestens ein Wort im Wörterbuch geladen werden. Die Worst-Case-Komplexität, um alle Knoten zu finden, die Wörter enthalten, ist O (kn), wobei n die Anzahl der Wörter im Wörterbuch ist und k der Wert ist maximale Anzahl der Buchstaben in einem Wort. Bei etwas eingeschränkten Mengen von Abfragebriefen sollte die Laufzeit jedoch pro Abfrage viel schneller sein.
"Unterschreiben" Sie die verfügbaren Buchstaben, indem Sie sie der Reihe nach sortieren; das ist O (m log m), wobei m die Anzahl der Buchstaben ist.
"Unterschreiben" Sie jedes Wort im Wörterbuch, indem Sie die Buchstaben des Wortes in der richtigen Reihenfolge sortieren; das ist O (k log k), wobei k die Länge des Wortes ist.
Vergleichen Sie die Buchstabensignatur mit jeder Wortsignatur; das ist O (min (m, k) * n), wobei n die Anzahl der Wörter im Wörterbuch ist. Gib ein beliebiges passendes Wort aus.
Wenn man eine englische Wortliste von ungefähr einer Viertelmillion Worten und nicht mehr als einem halben Dutzend annimmt, sollte das fast augenblicklich sein.
Ich wurde vor kurzem im BankBazaar-Interview dieselbe Frage gestellt. Mir wurde die Option gegeben (er sagte das auf eine sehr subtile Art und Weise), das Wörterbuch so zu bearbeiten, wie ich es möchte.
Mein erster Gedanke war, das Wörterbuch in einem Trie- oder Ternär-Suchbaum anzuordnen und alle Wörter aus den gegebenen Buchstaben zu machen. In jeder Optimierungsweise würde das n! + n-1! + n-2! n-3! + ..... + n Wortüberprüfungen (n ist die Anzahl der Buchstaben) im schlimmsten Fall, was nicht akzeptabel war.
Der andere Weg könnte sein, alle Wörterbuchwörter zu überprüfen, ob sie aus den gegebenen Buchstaben gemacht werden können. Dies wiederum würde in jeder optimierten Weise NoOfDictionaryWords (m) * durchschnittliche Größe von Wörterbuchwörtern (k) im schlimmsten Fall annehmen, was wiederum nicht akzeptabel war.
Jetzt habe ich n! + n-1! + n-2! + .... + N Wörter, die ich im Wörterbuch überprüfen muss, und ich möchte sie nicht alle überprüfen, also was sind die Situationen, in denen ich nur eine Teilmenge von ihnen überprüfen muss, und wie man sie gruppiert .
Wenn ich nur die Kombination und nicht die Permutation prüfen muss, wird das Ergebnis zu 2 ^ n.
Also muss ich die Wörterbuchwörter so vorverarbeiten, dass, wenn ich eine Kombination übergebe, alle Anagramme gedruckt würden.
A ds in etwa so: Ссылка Ein Hashwert, der aus den Buchstaben besteht (unabhängig von deren Position und Permutation) und auf eine Liste zeigt, die alle Wörter dieser Buchstaben enthält, dann müssen wir nur diesen Hashwert überprüfen.
Ich gab die Antwort, um den Hash-Wert zu erstellen, indem ich allen Alphabeten einen Primzahlwert zuwies und beim Berechnen des Hash-Wertes eines Wortes alle zugewiesenen Werte multiplizierte. Dies erzeugt ein Problem mit wirklich großen Hash-Werten, wenn man bedenkt, dass die 26. Primzahl 101 ist und viele Null-Werte in der Map Platz beanspruchen. Wir könnten es etwas optimieren, anstatt lexikografisch mit a = 2, b = 3, c = 5, d = 7 .... z = 101 zu beginnen, suchen wir nach den am häufigsten verwendeten Alphabeten und ordnen ihnen kleine Werte zu, wie Vokale und 's', 't' usw. Der Interviewer hat es akzeptiert, aber er hat die Antwort nicht erwartet, also gibt es definitiv eine andere Antwort, im Guten oder im Schlechten, aber da ist es.
Folgendes ist effizienter: -
%Vor%Dies wird für mehrere solche Abfragen ineffizient sein, so dass Sie Folgendes tun können: -
%Vor%.
Zeitkomplexität: -
Die obige Methode gibt O (1) Zeitkomplexität für eine Abfrage und O (N) Zeitkomplexität für Hashtabellenkonstruktion, wobei N keine Anzahl Wörter im Wörterbuch
(vgl. Anagrammsuche, zB Verwenden von Primzahlen sieht sauberer aus für einen signaturbasierten Ansatz - Sammeln für alle Nicht-Äquivalente "Teilstrings von letters "])
Angesichts des Anreizes würde ich Dict by (Vorkommen von Zeichen, die jedes Wort ausmachen, mit zunehmender Länge) anordnen und die Teilmengen von letters überprüfen, um die Gültigkeit jedes Wortes zu lange zu überprüfen.
Alternativ kann das Finden der Wörter aus dict aus char s aus letters als eine mehrdimensionale Bereichsabfrage betrachtet werden: mit "eeaspl" , die Buchstaben angeben, haben gültige Wörter null bis zwei "e", eins oder zwei keins von a, s, p, l und überhaupt keine anderen Zeichen - Grenzen für Wortlänge (nicht länger als letters , untere Grenze für Geschmack) fügen sich gut ein
Datenstrukturen wie k-d-trees funktionieren mit wenigen, selektiven Dimensionen.
(Möchte-Kommentar: Sie erwähnen nicht Alphabet Kardinalität, ob "gültig" hängt von Großschreibung oder Diakritika, "Komplexität" umfasst Programmierer Aufwand oder Vorverarbeitung von dict - Letzteres kann schwer zu amortisieren sein, wenn dict unveränderlich ist. )
Hier ist der Algorithmus, der alle Wörter findet, die aus einer Menge von Buchstaben in O(1) gebildet werden können. Wir werden Wörter mit ihren Spektren darstellen und sie in einem Präfixbaum (aka Trie) speichern.
Das Spektrum eines Worts W ist ein Array S der Größe N , so dass S(i) die Anzahl der Vorkommen (aka Häufigkeit ) eines A(i) -Briefes ist im Wort W , wobei A(i) der i -te Buchstabe eines ausgewählten Alphabets und N seine Größe ist.
Im englischen Alphabet ist A(0) beispielsweise A , A(1) ist B , ..., A(25) ist Z . Ein Spektrum des Wortes aha ist <2,0,0,0,0,0,0,1,0,...,0> .
Wir speichern das Wörterbuch in einem Präfix-Trie, indem wir das Spektrum als Schlüssel verwenden. Das erste Token eines Schlüssels ist die Häufigkeit des Buchstaben A , das zweite ist die Häufigkeit des Buchstaben B und so weiter. (Von hier und unten werden wir das englische Alphabet als Beispiel verwenden).
Einmal gebildet, wird unser Wörterbuch ein Baum mit der Höhe 26 und der Breite sein, die mit jedem Niveau, abhängig von einer Popularität des Buchstabens schwankt. Grundsätzlich wird jede Ebene eine Anzahl von Teilbäumen aufweisen, die der maximalen Worthäufigkeit dieses Buchstabens im bereitgestellten Wörterbuch entspricht.
Da unsere Aufgabe nicht nur darin besteht, zu entscheiden, ob wir ein Wort aus der vorgegebenen Menge von Zeichen zusammensetzen können, sondern auch, um diese Wörter zu finden (ein Suchproblem), müssen wir die Wörter an ihre Spektren anhängen nicht invertierbar, betrachte die Spektren der Wörter read und dear ). Wir werden ein Wort an das Ende jedes Pfades anhängen, der sein Spektrum darstellt.
Um herauszufinden, ob wir ein Wort aus einer bereitgestellten Menge erstellen können, erstellen wir ein Spektrum der Menge und finden alle Pfade im Präfix Trie mit den Frequenzen, die durch die entsprechenden Frequenzen des Spektrums der Menge begrenzt sind. (Beachten Sie, dass wir nicht gezwungen sind, alle Buchstaben aus der Menge zu verwenden. Wenn also ein Wort weniger Buchstaben verwendet, können wir es erstellen. Grundsätzlich ist unsere Anforderung, dass für alle Buchstaben des Wortes die Häufigkeit eines Buchstabens kleiner als sein sollte oder gleich einer Frequenz des gleichen Buchstabens in der bereitgestellten Menge).
Die Komplexität des Suchvorgangs hängt nicht von der Länge des Wörterbuchs oder der Länge der bereitgestellten Menge ab. Im Durchschnitt ist es gleich dem 26-fachen der durchschnittlichen Häufigkeit eines Briefes. Gegeben, englisches Wörterbuch, es ist ein ziemlich kleiner konstanter Faktor. Für andere Wörterbücher ist dies möglicherweise nicht der Fall.
Ich werde eine Referenzimplementierung eines Algorithmus in OCaml bereitstellen.
Der Dictionary-Datentyp ist rekursiv:
%Vor% (Hinweis: es ist nicht die beste Darstellung, wahrscheinlich ist es besser, es darzustellen ist eine Summenart, z. B. type t = Dict of t Int.Map.t | Data of string list , aber ich fand es einfacher, es mit der obigen Darstellung zu implementieren).
Wir können den Algorithmus durch eine Spektralfunktion verallgemeinern, entweder mit einem Funktor oder indem wir einfach die Spektralfunktion im Wörterbuch speichern, aber zur Vereinfachung werden wir nur das englische Alphabet in der ASCII-Darstellung fest codieren,
%Vor% Als nächstes definieren wir die Funktion add_word des Typs dict -> string -> dict , die unserem Wörterbuch einen neuen Pfad hinzufügt, indem wir ein Wort in sein Spektrum zerlegen und jedes Bestandteil hinzufügen. Jede Addition erfordert genau 26 Iterationen, die Spektrumberechnung nicht einschließend. Beachten Sie, dass die Implementierung rein funktional ist und keine imperativen Funktionen verwendet. Jedes Mal gibt die Funktion add_word eine neue Datenstruktur zurück.
Wir verwenden die folgende Definition des Wertes empty in der Funktion add :
Definieren wir nun die is_buildable -Funktion vom Typ dict -> string -> bool , die entscheiden wird, ob die gegebene Menge von Zeichen verwendet werden kann, um ein beliebiges Wort im Wörterbuch zu erstellen. Obwohl wir es über die Suche ausdrücken können, bevorzugen wir, wenn wir die Größe der gefundenen Menge überprüfen, eine spezialisierte Implementierung, da diese effizienter und leichter zu verstehen ist. Die Definition der Funktion folgt genau der oben gegebenen allgemeinen Beschreibung. Grundsätzlich prüfen wir für jedes Zeichen im Alphabet, ob im Wörterbuch ein Eintrag mit der Häufigkeit vorhanden ist, die kleiner oder gleich der Häufigkeit im Bausatz ist. Wenn wir alle Buchstaben geprüft haben, haben wir bewiesen, dass wir mit der gegebenen Menge mindestens ein Wort bilden können.
Lasst uns jetzt tatsächlich die Menge aller Wörter finden, die aus der bereitgestellten Menge zusammengebaut werden können:
%Vor% Wir werden grundsätzlich der Struktur der is_buildable -Funktion folgen, außer dass wir beweisen, dass eine solche Häufigkeit für jeden Buchstaben existiert, und wir werden alle Beweise sammeln, indem wir das Ende des Pfades erreichen und die angehängte Wortgruppe erfassen zu ihm.
Der Vollständigkeit halber werden wir es testen, indem wir ein kleines Programm erstellen, das ein Wörterbuch mit jedem Wort in einer separaten Zeile liest und mit einem Benutzer interagiert, indem wir nach einem Satz fragen und den Ersetzungssatz davon ausdrucken Worte, die daraus entstehen können.
%Vor% Hier kommt ein Beispiel für eine Interaktion, die /usr/share/dict/american-english dictionary auf meinem Rechner verwendet (Ubunty Trusty).
(Ja, das Wörterbuch enthält Wörter, die wie r und d wahrscheinlich keine echten englischen Wörter sind. In der Tat, für jeden Buchstaben hat das Wörterbuch ein Wort, also können wir grundsätzlich ein Wort aus jedem Wort zusammensetzen nicht leere Reihe von Buchstaben).
Die vollständige Implementierung und die Bauanleitung finden Sie auf Gist
Wenn Buchstaben wiederholt werden können, bedeutet dies, dass ein Wort unendlich lang sein kann. Sie würden dies natürlich auf die Länge des längsten Wortes im Wörterbuch beschränken, aber es gibt immer noch zu viele Wörter, die Sie überprüfen sollten. Wie empfohlen, würden Sie lieber über das Wörterbuch iterieren, um dies zu tun.
%Vor%Tags und Links algorithm
