Group Anagrams

+10

Du erhältst eine Liste von Wörtern strs. Zwei Wörter sind Anagramme, wenn das eine eine Umstellung des anderen ist: dieselben Buchstaben, die jeweils gleich oft verwendet werden. Ordne jedes Wort einer Gruppe mit all seinen Anagrammen zu und gib für jede Gruppe einen String zurück: die Wörter der Gruppe in alphabetischer Reihenfolge, durch einzelne Leerzeichen getrennt. Sortiere die Gruppen alphabetisch nach ihrem jeweils ersten Wort.

Ein Wort, das zweimal vorkommt, wird in seiner Gruppe zweimal aufgeführt, und ein Wort ohne Anagramm bildet eine Gruppe für sich. Alphabetisch bedeutet Wörterbuchreihenfolge: aab kommt vor ab und ab vor abc.

Funktion

groupAnagrams(strs: string-array) → string-array

strsstring-array: die zu gruppierenden Wörter, nur Kleinbuchstaben
Gibt zurückstring-array: eine Zeichenfolge pro Gruppe: ihre Wörter sortiert und durch Leerzeichen verbunden, Gruppen nach ihrem ersten Wort geordnet

Einschränkungen

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Jedes Wort besteht ausschließlich aus englischen Kleinbuchstaben.

Beispiele

Eingabe: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Ausgabe: ["apple", "enlist listen silent", "notes onset stone tones"]
Erklärung: enlist, listen und silent verwenden jeweils e, i, l, n, s und t genau einmal. notes, onset, stone und tones haben e, n, o, s und t gemeinsam, und apple passt zu nichts. Nach dem ersten Wort geordnet lauten die Gruppen apple, enlist, notes.

Eingabe: strs = ["race", "arc", "care", "car", "acre"]
Ausgabe: ["acre care race", "arc car"]
Erklärung: acre, care und race enthalten a, c, e und r. arc und car enthalten kein e und bilden daher ihre eigene Gruppe. acre kommt vor arc, weil c an zweiter Stelle vor r kommt.

Eingabe: strs = ["b", "a", "b"]
Ausgabe: ["a", "b b"]
Erklärung: Die beiden Exemplare von b sind Anagramme voneinander und bleiben beide in der Gruppe. a hat keinen Partner und kommt zuerst.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, die Wörter könnten beliebige Unicode-Zeichen statt 26 Kleinbuchstaben enthalten. Welche der beiden Schlüssel, sortierte Buchstaben oder Buchstabenzählungen, funktioniert weiterhin, und was würdest du daran ändern?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jedes Wort mit jedem anderen Wort zu vergleichen funktioniert, kostet aber für jedes Paar einen vollständigen Vergleich. Der Schlüssel zur Lösung ist ein kanonischer Schlüssel: ein Wert, den du aus einem einzelnen Wort berechnest und der für alle seine Anagramme gleich und für jedes andere Wort verschieden ist. Die Buchstaben eines Wortes in sortierter Reihenfolge bilden einen solchen Schlüssel, und eine Hash-Map, die Schlüssel Gruppen zuordnet, macht aus der Gruppierung einen einzigen Durchlauf. Die erforderliche Reihenfolge ergibt sich von selbst, wenn du die Wörter sortierst, bevor du sie gruppierst.

Vergleiche jedes Wort mit jeder Gruppe

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Anagrammgleichheit ist transitiv: Wenn stone zu notes passt und notes zu tones passt, dann passt stone zu tones. Ein neues Wort muss also nie mit jedem Mitglied einer Gruppe verglichen werden. Der Vergleich mit dem ersten Wort der Gruppe entscheidet, ob es dazugehört.

Um zwei Wörter zu vergleichen, zählt man die Buchstaben. Sie sind Anagramme, wenn sie dieselbe Länge haben und jeder Buchstabe im einen Wort genauso oft vorkommt wie im anderen. Addiere für jeden Buchstaben des ersten Wortes 1 und ziehe für jeden Buchstaben des zweiten Wortes 1 ab. Prüfe dann, ob alle 26 Zähler bei 0 enden.

Sortiere zuerst die Eingabe, dann ergibt sich die Reihenfolge von selbst. Die Wörter treffen alphabetisch sortiert ein, und jedes wird ans Ende seiner Gruppe angefügt, sodass jede Gruppe sortiert bleibt. Eine Gruppe wird erstellt, wenn ihr alphabetisch erstes Wort eintrifft, daher sind die Gruppen bereits nach ihrem jeweils ersten Wort geordnet.

Der Aufwand entsteht beim Durchsuchen. Wenn keine zwei Wörter Anagramme sind, wird jedes Wort mit jeder vorherigen Gruppe verglichen: Bei 4000 Wörtern ergeben sich etwa 4000 × 3999 / 2 ≈ 8 × 10^6 Vergleiche, bei denen jeweils bis zu 8 Buchstaben und 26 Zähler berücksichtigt werden. Das ist für Python, Lua und R bei den größten Tests zu langsam, und da der Aufwand quadratisch mit der Listenlänge wächst, würde es bei 10^5 Wörtern jede Sprache überfordern.

Algorithmus

Sortiere die Wörter alphabetisch.
Führe eine Liste von Gruppen, die jeweils eine Liste von Wörtern enthalten.
Suche für jedes Wort nach einer Gruppe, deren erstes Wort dieselben Buchstabenhäufigkeiten aufweist, und füge das Wort dieser Gruppe hinzu.
Wenn keine Gruppe passt, beginne eine neue Gruppe, die nur dieses Wort enthält.
Verbinde die Wörter jeder Gruppe mit einzelnen Leerzeichen und gib die Gruppen in der Reihenfolge zurück, in der du sie erstellt hast.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

Nach sortierten Buchstaben in einer Hash-Map gruppieren

Idee

Anstatt zu fragen, zu welcher Gruppe ein Wort passt, berechne den Namen der Gruppe aus dem Wort selbst. Sortiere die Buchstaben eines Wortes, und alle seine Anagramme ergeben denselben Text: listen, silent und enlist werden alle zu eilnst, während stone zu enost wird. Zwei Wörter haben genau dann dieselbe sortierte Form, wenn sie dieselben Buchstaben gleich oft enthalten – das ist die Definition eines Anagramms. Die sortierte Form ist also ein kanonischer Schlüssel für die Gruppe.

Eine Hash-Map, die Schlüssel auf Wortlisten abbildet, gruppiert dann alles in einem Durchlauf. Für jedes Wort sind eine Sortierung von höchstens 8 Buchstaben und ein Nachschlagen in der Map nötig; mit einem Wort aus einer anderen Gruppe wird es nie verglichen.

Für die Reihenfolge sortiere die Eingabe vor dem Gruppieren, wie beim ersten Ansatz. Die Wörter kommen alphabetisch an, sodass sich jede Liste der Reihe nach füllt und ein Schlüssel in die Map gelangt, sobald das erste Wort seiner Gruppe eintrifft. Maps, die die Einfügereihenfolge beibehalten (ein Python dict, eine JavaScript Map, eine Java LinkedHashMap, eine Dart map, Ruby-Hashes und PHP-Arrays), geben die Gruppen in dieser Reihenfolge zurück. Wenn die Map keine Reihenfolge hat, speichere den Index jeder Gruppe in der Map und die Gruppen selbst in einer Liste.

Das Sortieren der Eingabe erfordert etwa n log n Vergleiche von jeweils bis zu k Buchstaben, also ungefähr 5 × 10^4 Wortvergleiche bei 4000 Wörtern statt 8 × 10^6. Das Erstellen der Schlüssel fügt O(n · k log k) hinzu, was im Vergleich dazu wenig ist, weil k ≤ 8.

Algorithmus

Sortiere die Wörter alphabetisch.
Erstelle für jedes Wort seinen Schlüssel, indem du seine Buchstaben sortierst.
Suche den Schlüssel in einer Hash-Map. Wenn er neu ist, lege eine leere Gruppe dafür an und behalte die Reihenfolge bei, in der du die Gruppen erstellst.
Füge das Wort der Gruppe seines Schlüssels hinzu.
Gib die Wörter jeder Gruppe mit einzelnen Leerzeichen verbunden zurück, wobei die Gruppen in der Reihenfolge ihrer Erstellung stehen.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

Stolperfallen und Grenzfälle

Die Gruppierung ist der Teil, den man üben muss. Die meisten falschen Antworten bei dieser Version entstehen durch die Reihenfolge der Ausgabe und durch Schlüssel, die nicht eindeutig sind.

Die Gruppen nach ihrem Schlüssel statt nach ihrem ersten Wort ordnen. Ein Schlüssel ist die kleinste Umordnung seiner Buchstaben, nicht eines der Wörter selbst: Für ["cab", "bad"] lauten die Schlüssel abc und abd. Dadurch würde cab an erster Stelle stehen, aber nach dem ersten Wort kommt bad zuerst.
Wörter in einer Menge sammeln. ["b", "a", "b"] muss b b ergeben; eine Menge behält nur eine Kopie.
Einen Schlüssel bilden, der nur die unterschiedlichen Buchstaben berücksichtigt. ab und aabb verwenden dieselben zwei Buchstaben, aber aabb enthält jeden zweimal, daher sind sie keine Anagramme.
Einen Schlüssel verwenden, der die Buchstabencodes addiert. ad und bc haben dieselbe Summe, daher fasst eine Summe Wörter zusammen, die keinen Buchstaben gemeinsam haben.
Jede Gruppe sortieren, aber nicht die Eingabe, und dann vergessen, die Gruppen zu sortieren. Die Einfügereihenfolge entspricht dann der Reihenfolge der Eingabe und nicht der Reihenfolge der ersten Wörter.
Die Gruppen von Hand zusammenfügen und am Anfang oder Ende der Zeichenfolge einer Gruppe ein Leerzeichen stehen lassen.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Group Anagrams?

Bei einer Hashmap mit sortierten Buchstaben als Schlüssel benötigt das Erstellen der Schlüssel für n Wörter mit bis zu k Buchstaben O(n · k log k), und die Arbeit mit der Map beträgt O(n · k). Diese Version sortiert außerdem die Wörter, um die Ausgabe zu ordnen, was zusätzlich O(n · k · log n) benötigt. Der Speicherbedarf beträgt O(n · k) für die Schlüssel und die Gruppen.

Ist ein Buchstabenzähler schneller als das Sortieren jedes Wortes?

Ein Zählschlüssel, die 26 Buchstabenzahlen ausgeschrieben als Text wie 1#0#2#…, benötigt O(k) Zeit statt O(k log k) und ist daher bei langen Wörtern schneller. Bei Wörtern mit höchstens 8 Buchstaben ist das Sortieren genauso schnell, und das alphabetische Sortieren der Ausgabe kostet mehr als jeder der beiden Schlüssel. Beide Schlüssel sind korrekt, denn zwei Wörter haben genau dann dieselben Buchstabenzahlen, wenn sie dieselben sortierten Buchstaben haben.

Warum nicht die Summe der Buchstabencodes als Schlüssel verwenden?

Verschiedene Buchstaben können dieselbe Summe ergeben: a + d ist gleich b + c, daher würden ad und bc in dieselbe Gruppe fallen. Ein Schlüssel muss für Anagramme gleich und für alles andere verschieden sein, und die sortierten Buchstaben oder die vollständige Anzahl jedes Buchstabens garantieren das. Die Multiplikation mit einer Primzahl pro Buchstaben ist ebenfalls exakt, aber bei 101 für z läuft ein Wort aus zehn z bereits bei einer 64-Bit-Ganzzahl über.

Warum sollte die Eingabe vor dem Gruppieren sortiert werden?

Die Antwort verlangt nach sortierten Gruppen, die nach ihrem ersten Wort geordnet sind. Wenn alle Wörter einmal sortiert werden, erhält man beides: Jede Gruppe bekommt ihre Wörter in alphabetischer Reihenfolge, und eine Gruppe wird erstellt, sobald ihr erstes Wort eintrifft. Jede Gruppe anschließend zu sortieren und dann die Gruppen nach ihrem ersten Wort zu ordnen, führt mit mehr Code zum selben Ergebnis.

Python

def groupAnagrams(strs):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

Erwartet

["apple", "enlist listen silent", "notes onset stone tones"]