Am besten Algorithmus zu finden Anagramm des Wortes aus dictonary

Mich war das ein problem, so etwas wie dieses

Habe ich eine Liste, die ist im Wörterbuch mit Millionen von Wörtern, und ich bin da input ein Wort wie OSPT onlt 2 Wörter die gebildet werden können, STOP und POST..
Ich möchte herausfinden, alle Anagramm gleiche Wörter in dictonary in optimierter Weise.

Was ich gelöst.

Gab ich unten die Lösung.Ich nehme das Wort und permutiert Sie Sie und markieren das Wort existiert im Wörterbuch oder nicht.Aber ist das n*n nicht optimiert.Gibt es eine Möglichkeit, dieses Problem zu lösen

  • wie würde das helfen?
InformationsquelleAutor chiru | 2013-12-19
  1. 5

    Sortieren Sie die Zeichen in jedem Wort alphabetisch nach Schlüssel in form einer Karte, deren Werte sind die Listen der Wörter, die für diese Taste.

    Wenn Sie ein Wort gegeben zu finden, der anagramme für Sortieren Sie die Zeichen in word alphabetisch und tun eine Suche in der Karte.

    Durch Ihr Beispiel und durch das Wort POOL, Sie bekommen würde:

    LOOP -> [LOOP, POOL, POLO]
OPST -> [STOP, POST]

    Den Java-code wäre so etwas wie:

    public class AnagramGenerator
{
  private Map<String, Collection<String>> indexedDictionary;

  public AnagramGenerator(List<String> dictionary)
  {
    this.indexedDictionary = index(dictionary);
  }

  public Collection<String> getAnagrams(String word)
  {
    return indexedDictionary.get(sort(word));
  }


  private Map<String, Collection<String>> index(List<String> dictionary)
  {
    MultiMap<String, String> indexedDictionary = HashMultimap.create();

    for (String word : dictionary)
    {
      indexDictionary.put(sort(word), word);
    }

    return indexedDictionary.asMap();
  }

  private String sort(String word) 
  {
    List<Character> sortedCharacters= Arrays.asList(word.toCharArray());
    Collections.sort(sortedCharacters);

    StringBuilder builder = new StringBuilder();
    for (Character character : sortedCharacters)
    {
      builder.append(character);
    }

    return builder.toString();
  }
}
    InformationsquelleAutor Nick Holt
  2. 4

    Können Sie dies tun.

    • Art jedes Wort und fügen Sie es auf eine MultiMap sortiert von Wort zu Wort.
    • jedes Wort zu verwenden, wie ein Anagramm, indem Sie Sie Sortieren das Wort zuerst.

    Den index kostet einmal, und O(N), wo N ist die Anzahl der Wörter.

    Nach, dass die Kosten für das Sortieren ist O(M log M) Sortieren die Briefe, wo M ist die Anzahl der Buchstaben. Dies ist sehr Billig im Vergleich zu den Kosten der Berechnung von Permutationen.

    BTW Dieser Ansatz, die Worte werden nur einmal gescannt, im Voraus.

    InformationsquelleAutor Peter Lawrey
  3. 4

    Kann dies auf folgende Weise:

    Für das gegebene Wort halten, eine Zählung aller Zeichen. Zum Beispiel für OSTP, 

    count['O'] = 1;
count['S'] = 1;
count['T'] = 1;
count['P'] = 1;

    Können Sie ein array mit 26 Elementen wie diesem.

    Dann während der Iteration durch das Wörterbuch, prüfen Sie einfach, welches Wort hat die gleiche Anzahl Zeichen.

    InformationsquelleAutor Abhishek Bansal
  4. 1

    Können Sie Vorverarbeiten Ihrer Liste: ersetzen Sie jedes Wort mit seiner sortiert Anagramm (d.h. abacaba wird aaaabbc). Diese Zeichenfolge eindeutig repräsentiert ein beliebiges Wort, das ist das Anagramm zu dem Wort aus dem Wörterbuch.

    Dann, wenn Sie erhalten eine Abfrage, Sortieren, Buchstaben und prüfen, ob dieses Wort wird in aufbereiteter Wörterbuch.

    InformationsquelleAutor Ivan Smirnov
  5. 1

    Für beste Geschwindigkeit, Sie können die Karte der Zeichen, der in einzelne prime-Werte, multiplizieren Sie (stellen Sie sicher, dass Sie groß genug zahlen), und verwenden Sie das Produkt als eine numerische Taste für die Speicherung der gültigen Permutationen. Jede Zahl ist einzigartig für die gegebene Menge von Permutationen wie die Charaktere bilden eine einzigartige prime Aufspaltung.

    Gegeben, ein Wort, wiederholen Sie den Vorgang, um den Wert und Zugriff auf das Wörterbuch direkt mit dass. Ähnlich sortiert, Saiten-Lösung, sondern spart den Aufwand der Sortierung und vereinfacht die Schlüssel-Vergleiche.

    Siehe auch hier für eine Verwandte Lösung in c - Generieren gleichen eindeutigen hash-code für alle anagramme

    InformationsquelleAutor Leeor
Schreibe einen Kommentar