Group Anagrams

+10

Du erhältst eine Liste von Wörtern strs. Zwei Wörter sind Anagramme, wenn man die Buchstaben des einen so umordnet, dass sie den Buchstaben des anderen entsprechen, wobei jeder Buchstabe gleich oft verwendet wird. Gruppiere jedes Wort mit all seinen Anagrammen und gib für jede Gruppe einen String zurück: ihre Wörter in alphabetischer Reihenfolge, durch einzelne Leerzeichen getrennt. Sortiere die Gruppen alphabetisch nach ihrem ersten Wort.

Ein wiederholtes Wort 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 Wörter gruppieren, nur Kleinbuchstaben
Gibt zurückstring-array: eine Zeichenkette 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 enthält ausschließlich englische 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 einmal e, i, l, n, s und t. notes, onset, stone und tones haben e, n, o, s und t gemeinsam. apple passt zu keinem und steht beim ersten Wort vorne.

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 Kopien von b sind Anagramme voneinander, und beide bleiben in der Gruppe. a hat keinen Partner und kommt zuerst.

Weiterführende Frage

Wenn die Wörter beliebige Unicode-Zeichen enthalten könnten: Welcher Schlüssel – sortierte Buchstaben oder Buchstabenhäufigkeiten – 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

Berechne für jedes Wort allein einen Schlüssel, 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 auf Gruppen abbildet, sammelt die Gruppen in einem Durchlauf. Sortiere die Wörter zuerst, dann ergibt sich die erforderliche Reihenfolge ganz von selbst.

Vergleiche jedes Wort mit jeder Gruppe

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

Idee

Führe eine Liste von Gruppen und vergleiche jedes Wort mit dem ersten Wort jeder Gruppe. Anagramme sind transitiv, daher entscheidet ein Vergleich pro Gruppe über die Zugehörigkeit. Zwei Wörter sind Anagramme, wenn sie dieselbe Länge und dieselbe Anzahl jeder der 26 Buchstaben haben. Sortiere zuerst die Eingabe: Dann füllt sich jede Gruppe in alphabetischer Reihenfolge, und die Gruppen werden in der Reihenfolge ihres ersten Wortes erstellt.

Wenn keine zwei Wörter Anagramme sind, wird jedes Wort mit allen vorherigen Gruppen verglichen: 4000 Wörter ergeben etwa 8 × 10^6 Vergleiche, bei denen jeweils bis zu 8 Buchstaben und 26 Zähler berücksichtigt werden.

Algorithmus

Sortiere die Wörter alphabetisch.
Finde für jedes Wort eine Gruppe, deren erstes Wort dieselbe Buchstabenanzahl hat, und füge das Wort hinzu. Wenn keine passt, beginne eine neue Gruppe.
Gib die Wörter jeder Gruppe, durch einzelne Leerzeichen getrennt, in der Reihenfolge ihrer Erstellung zurück.

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

Berechne den Namen der Gruppe aus dem Wort selbst. Sortiere die Buchstaben eines Wortes, und jedes Anagramm ergibt 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. Eine Hash-Map, die Schlüssel Wortlisten zuordnet, gruppiert dann alles in einem Durchlauf, und kein Wort wird mit einer anderen Gruppe verglichen.

Die Reihenfolge ergibt sich wie zuvor durch das vorherige Sortieren der Eingabe: Jede Liste wird alphabetisch gefüllt, und ein Schlüssel kommt in die Map, sobald das erste Wort seiner Gruppe eintrifft. Eine Map, die die Einfügereihenfolge beibehält, gibt die Gruppen in dieser Reihenfolge zurück; andernfalls speichere die Gruppen in einer Liste und ordne jedem Schlüssel seinen Index zu.

Das Sortieren der Eingabe kostet bei 4000 Wörtern etwa 5 × 10^4 Wortvergleiche statt 8 × 10^6.

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. Ist er neu, beginne eine leere Gruppe dafür und behalte die Reihenfolge bei, in der du die Gruppen erstellst.
Füge das Wort der Gruppe zu seinem Schlüssel hinzu.
Gib die Wörter jeder Gruppe durch einzelne Leerzeichen getrennt 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 Gruppen nach dem Schlüssel statt nach dem ersten Wort sortieren. Bei ["cab", "bad"] sorgen die Schlüssel abc und abd dafür, dass cab zuerst kommt, aber bad sollte an erster Stelle stehen.
Wörter in einer Menge sammeln. ["b", "a", "b"] muss b b ergeben; eine Menge behält jedes Element nur einmal.
Einen Schlüssel erstellen, der nur aus den unterschiedlichen Buchstaben besteht. ab und aabb verwenden dieselben zwei Buchstaben, sind aber keine Anagramme.
Jede Gruppe sortieren, aber nicht die Eingabe und auch nicht die Gruppen. Die Einfügereihenfolge folgt dann der Eingabe und nicht den ersten Wörtern.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Group Anagrams?

Das Erstellen der Schlüssel aus sortierten Buchstaben benötigt O(n · k log k) für n Wörter mit bis zu k Buchstaben, und der Aufwand für die Map beträgt O(n · k). Das Sortieren der Wörter, um die Ausgabe zu ordnen, benötigt zusätzlich O(n · k · log n), was den Aufwand dominiert. 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 als Text, zum Beispiel 1#0#2#…, benötigt O(k) statt O(k log k) und ist daher bei langen Wörtern schneller. Bei 8 Buchstaben oder weniger ist das Sortieren genauso schnell. Beide Schlüssel sind exakt: Zwei Wörter haben genau dann dieselben Zählwerte, 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 derselben Gruppe angehören. Ein Produkt aus einer Primzahl pro Buchstabe ist exakt, aber bei 101 für z läuft ein Wort aus zehn z über eine 64-Bit-Ganzzahl über.

def groupAnagrams(strs):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

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