Group Anagrams

Q: Jaka jest złożoność czasowa grupowania anagramów?

Tworzenie kluczy z posortowanymi literami zajmuje O(n · k log k) dla n słów o długości do k liter, a operacje na mapie mają złożoność O(n · k) . Sortowanie słów w celu uporządkowania wyniku dodaje O(n · k · log n) , co dominuje. Złożoność pamięciowa wynosi O(n · k) dla kluczy i grup.

ŚrednieHaszowanie Sortowanie

+10

Otrzymujesz listę słów strs. Dwa słowa są anagramami, gdy jedno powstaje przez przestawienie liter drugiego, przy czym każda litera występuje tyle samo razy. Zgrupuj każde słowo ze wszystkimi jego anagramami i zwróć jeden ciąg znaków dla każdej grupy: jej słowa w kolejności alfabetycznej, połączone pojedynczymi spacjami. Uporządkuj grupy alfabetycznie według ich pierwszego słowa.

Powtórzone słowo występuje w swojej grupie dwa razy, a słowo bez anagramów tworzy grupę jednoelementową. Kolejność alfabetyczna oznacza porządek słownikowy: aab występuje przed ab, a ab przed abc.

Funkcja

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

strsstring-array: słowa do pogrupowania, tylko małe litery
Zwracastring-array: jeden ciąg na grupę: jego słowa posortowane i połączone spacjami, grupy uporządkowane według pierwszego słowa

Ograniczenia

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Każde słowo składa się wyłącznie z małych liter alfabetu angielskiego.

Przykłady

Wejście: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Wyjście: ["apple", "enlist listen silent", "notes onset stone tones"]
Wyjaśnienie: enlist, listen i silent używają każdej z liter e, i, l, n, s i t dokładnie raz. notes, onset, stone i tones mają wspólne litery e, n, o, s i t. apple nie pasuje do niczego, a według pierwszego słowa prowadzi.

Wejście: strs = ["race", "arc", "care", "car", "acre"]
Wyjście: ["acre care race", "arc car"]
Wyjaśnienie: acre, care i race mają wspólne litery a, c, e i r. arc i car nie mają litery e, więc tworzą własną grupę. acre występuje przed arc, ponieważ c jest przed r na drugiej pozycji.

Wejście: strs = ["b", "a", "b"]
Wyjście: ["a", "b b"]
Wyjaśnienie: Dwie kopie b są swoimi anagramami i obie pozostają w grupie. a nie ma pary i występuje jako pierwsza.

Pytanie dodatkowe

Jeśli słowa mogą zawierać dowolne znaki Unicode, który klucz — posortowane litery czy liczba wystąpień każdej litery — nadal będzie działać i co byś w nim zmienił?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Oblicz klucz dla każdego słowa z osobna, który jest taki sam dla wszystkich jego anagramów i różny dla każdego innego słowa. Litery słowa w kolejności alfabetycznej stanowią taki klucz, a mapa haszująca, która przyporządkowuje klucz do grupy, zbiera grupy w jednym przebiegu. Najpierw posortuj słowa, a wymagana kolejność pojawi się sama.

Porównaj każde słowo z każdą grupą

Poprawne, ale nie kończy się na największych testach

Intuicja

Przechowuj listę grup i porównuj każde słowo z pierwszym słowem każdej grupy. Bycie anagramami jest relacją przechodnią, więc jedno porównanie na grupę wystarczy, by zdecydować o przynależności. Dwa słowa są anagramami, gdy mają tę samą długość i taką samą liczbę wystąpień każdej z 26 liter. Najpierw posortuj dane wejściowe: wtedy każda grupa zapełnia się w kolejności alfabetycznej, a grupy są tworzone w kolejności ich pierwszych słów.

Jeśli żadne dwa słowa nie są anagramami, każde słowo trzeba porównać ze wszystkimi wcześniejszymi grupami: 4000 słów daje około 8 × 10^6 porównań, z których każde obejmuje do 8 liter i 26 liczników.

Algorytm

Posortuj słowa alfabetycznie.
Dla każdego słowa znajdź grupę, której pierwsze słowo ma taką samą liczbę liter, i dodaj do niej to słowo. Jeśli żadna grupa nie pasuje, utwórz nową.
Zwróć słowa z każdej grupy połączone pojedynczymi spacjami, w kolejności tworzenia grup.

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]

Grupowanie według posortowanych liter w mapie haszującej

Intuicja

Wyznacz nazwę grupy na podstawie samego słowa. Posortuj litery słowa, a każdy anagram da ten sam tekst: listen, silent i enlist wszystkie zmieniają się w eilnst, a stone zmienia się w enost. Dwa słowa mają tę samą posortowaną postać dokładnie wtedy, gdy zawierają te same litery tyle samo razy, co stanowi definicję anagramu. Mapa haszująca, która przyporządkowuje klucz do listy słów, grupuje je wszystkie w jednym przebiegu i żadne słowo nie jest porównywane ze słowem z innej grupy.

Kolejność wynika z wcześniejszego posortowania danych wejściowych: każda lista zapełnia się alfabetycznie, a klucz trafia do mapy, gdy pojawia się pierwsze słowo z danej grupy. Mapa zachowująca kolejność wstawiania zwraca grupy w tej kolejności; w przeciwnym razie przechowuj grupy na liście i przyporządkuj każdy klucz do indeksu.

Posortowanie danych wejściowych wymaga około 5 × 10^4 porównań słów dla 4000 słów zamiast 8 × 10^6.

Algorytm

Posortuj słowa alfabetycznie.
Dla każdego słowa utwórz klucz, sortując jego litery.
Wyszukaj klucz w mapie haszującej. Jeśli jest nowy, utwórz dla niego pustą grupę, zachowując grupy w kolejności ich tworzenia.
Dodaj słowo do grupy przypisanej do jego klucza.
Zwróć słowa z każdej grupy połączone pojedynczymi spacjami, a grupy w kolejności ich tworzenia.

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()]

Pułapki i przypadki brzegowe

Porządkowanie grup według klucza zamiast według pierwszego słowa. Dla ["cab", "bad"] klucze abc i abd sprawiają, że cab pojawia się jako pierwsze, ale pierwsze powinno być bad.
Zbieranie słów w zbiorze. ["b", "a", "b"] musi dać b b; zbiór przechowuje tylko jedną kopię.
Klucz zbudowany wyłącznie z różnych liter. ab i aabb używają tych samych dwóch liter, ale nie są anagramami.
Sortowanie każdej grupy, ale nie danych wejściowych ani grup. Kolejność wstawiania będzie wtedy zgodna z danymi wejściowymi, a nie z pierwszymi słowami.

Najczęstsze pytania3

Jaka jest złożoność czasowa grupowania anagramów?

Tworzenie kluczy z posortowanymi literami zajmuje O(n · k log k) dla n słów o długości do k liter, a operacje na mapie mają złożoność O(n · k). Sortowanie słów w celu uporządkowania wyniku dodaje O(n · k · log n), co dominuje. Złożoność pamięciowa wynosi O(n · k) dla kluczy i grup.

Czy zliczanie liter za pomocą klucza jest szybsze niż sortowanie każdego słowa?

Klucz zliczeń, czyli zliczenia 26 liter zapisane jako tekst, na przykład 1#0#2#…, wymaga O(k) zamiast O(k log k), więc sprawdza się lepiej w przypadku długich słów. Przy 8 literach lub mniej sortowanie jest równie szybkie. Oba klucze są dokładne: dwa słowa mają takie same zliczenia wtedy i tylko wtedy, gdy mają takie same posortowane litery.

Dlaczego nie użyć sumy kodów liter jako klucza?

Różne litery mogą dawać tę samą sumę: a + d równa się b + c, więc ad i bc trafiłyby do tej samej grupy. Iloczyn jednej liczby pierwszej przypisanej każdej literze jest dokładny, ale przy 101 dla z słowo składające się z dziesięciu liter z powoduje przepełnienie 64-bitowej liczby całkowitej.

def groupAnagrams(strs):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

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