Group Anagrams

+10

Otrzymujesz listę słów strs. Dwa słowa są anagramami, gdy jedno jest przestawieniem liter drugiego: zawierają te same litery, każdą użytą tyle samo razy. Umieść każde słowo w grupie zawierającej wszystkie jego anagramy i zwróć jeden ciąg znaków dla każdej grupy: słowa z grupy w kolejności alfabetycznej, połączone pojedynczymi spacjami. Uporządkuj grupy alfabetycznie według ich pierwszego słowa.

Słowo, które występuje dwa razy, jest wymienione w swojej grupie dwa razy, a słowo bez anagramów tworzy jednoelementową grupę. Kolejność alfabetyczna oznacza kolejność słownikową: aab występuje przed ab, a ab przed abc.

Funkcja

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

strsstring-array: słowa do pogrupowania, wyłącznie małe litery
Zwracastring-array: jeden ciąg znaków 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 zawiera wyłącznie małe litery 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 zawierają po jednym wystąpieniu liter e, i, l, n, s i t. notes, onset, stone i tones zawierają litery e, n, o, s i t, a apple do niczego nie pasuje. Według pierwszego słowa grupy to apple, enlist, notes.

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 pierwsze.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że słowa mogą zawierać dowolne znaki Unicode, a nie tylko 26 małych liter. Który z tych dwóch kluczy — posortowane litery czy liczba wystąpień poszczególnych liter — nadal działa i co należałoby w nim zmienić?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Porównywanie każdego słowa z każdym innym działa, ale wymaga pełnego porównania dla każdej pary. Problem rozwiązuje klucz kanoniczny: wartość obliczana na podstawie jednego słowa, która jest taka sama dla wszystkich jego anagramów i inna dla każdego innego słowa. Litery słowa ułożone w kolejności alfabetycznej stanowią taki klucz, a mapa hashująca przypisująca klucz do grupy pozwala pogrupować słowa w jednym przebiegu. Wymaganą kolejność otrzymasz bez dodatkowego wysiłku, jeśli posortujesz słowa przed ich grupowaniem.

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

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

Intuicja

Relacja bycia anagramami jest przechodnia: jeśli stone pasuje do notes, a notes pasuje do tones, to stone pasuje do tones. Nowe słowo nigdy nie musi więc pasować do każdego elementu grupy. Porównanie go z pierwszym słowem grupy rozstrzyga, czy do niej należy.

Aby porównać dwa słowa, policz litery. Są anagramami, gdy mają tę samą długość i każda litera występuje w jednym z nich tyle samo razy co w drugim. Dodaj 1 za każdą literę pierwszego słowa i odejmij 1 za każdą literę drugiego, a następnie sprawdź, czy wszystkie 26 liczników mają wartość 0.

Najpierw posortuj dane wejściowe, a kolejność ustali się sama. Słowa pojawiają się alfabetycznie i każde dołącza na końcu swojej grupy, więc każda grupa pozostaje posortowana. Grupa powstaje, gdy pojawia się jej pierwsze alfabetycznie słowo, dlatego grupy są już uporządkowane według pierwszego słowa.

Koszt stanowi przeglądanie listy. Gdy żadne dwa słowa nie są anagramami, każde słowo jest porównywane ze wszystkimi wcześniejszymi grupami: 4000 słów oznacza około 4000 × 3999 / 2 ≈ 8 × 10^6 porównań, z których każde obejmuje do 8 liter i 26 liczników. To zbyt wolne dla Pythona, Lua i R przy największych testach, a ilość pracy rośnie proporcjonalnie do kwadratu długości listy, więc przy 10^5 słowach algorytm byłby zbyt wolny w każdym języku.

Algorytm

Posortuj słowa alfabetycznie.
Przechowuj listę grup, z których każda jest listą słów.
Dla każdego słowa poszukaj grupy, której pierwsze słowo ma taki sam rozkład liter, i dodaj do niej to słowo.
Jeśli żadna grupa nie pasuje, utwórz nową grupę zawierającą tylko to słowo.
Połącz słowa w każdej grupie, używając pojedynczych spacji, i zwróć grupy w kolejności ich utworzenia.

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

Zamiast pytać, do której grupy pasuje dane słowo, oblicz nazwę grupy na podstawie samego słowa. Posortuj litery słowa — wtedy wszystkie jego anagramy dadzą ten sam tekst: listen, silent i enlist zmienią się w eilnst, a stone 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. Posortowana postać jest więc kanonicznym kluczem grupy.

Mapa haszująca, w której kluczem jest ta postać, a wartością lista słów, grupuje je wszystkie w jednym przebiegu. Każde słowo wymaga jednego sortowania maksymalnie 8 liter i jednego wyszukania w mapie; nigdy nie jest porównywane ze słowem z innej grupy.

Aby zachować kolejność, posortuj dane wejściowe przed grupowaniem, tak jak w pierwszym podejściu. Słowa pojawiają się alfabetycznie, więc każda lista zapełnia się w tej kolejności, a klucz trafia do mapy, gdy pojawia się pierwsze słowo z danej grupy. Mapy zachowujące kolejność wstawiania (słownik Python, Map JavaScript, LinkedHashMap Java, mapa Dart, hasze Ruby i tablice PHP) zwracają grupy w tej kolejności. Jeśli mapa nie zachowuje kolejności, przechowuj w niej indeks każdej grupy, a same grupy zapisuj na liście.

Sortowanie danych wejściowych wymaga około n log n porównań, z których każde obejmuje maksymalnie k liter — dla 4000 słów to mniej więcej 5 × 10^4 porównań słów zamiast 8 × 10^6. Tworzenie kluczy wymaga dodatkowo O(n · k log k), co stanowi niewielki koszt w porównaniu, ponieważ k ≤ 8.

Algorytm

Posortuj słowa alfabetycznie.
Dla każdego słowa utwórz klucz, sortując jego litery.
Wyszukaj klucz w mapie mieszającej. Jeśli jest nowy, utwórz dla niego pustą grupę, zachowując kolejność tworzenia grup.
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 utworzenia.

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

Grupowanie to część, którą trzeba przećwiczyć. Większość błędnych odpowiedzi w tej wersji wynika z kolejności danych wyjściowych oraz z kluczy, które nie są unikalne.

Sortowanie grup według ich klucza zamiast pierwszego słowa. Klucz to najmniejsze przestawienie liter w słowach, a nie jedno z tych słów: dla ["cab", "bad"] kluczami są abc i abd, co umieściłoby cab na pierwszym miejscu, ale według pierwszego słowa bad jest pierwsze.
Zbieranie słów w zbiorze. ["b", "a", "b"] musi dać b b; zbiór zachowuje tylko jedną kopię.
Klucz zbudowany wyłącznie z różnych liter. ab i aabb składają się z tych samych dwóch liter, ale aabb zawiera po dwie z każdej, więc nie są anagramami.
Klucz będący sumą kodów liter. ad i bc mają tę samą sumę, więc suma łączy słowa, które nie mają żadnej wspólnej litery.
Sortowanie każdej grupy, ale nie danych wejściowych, a następnie zapomnienie o posortowaniu grup. Kolejność wstawiania jest wtedy kolejnością danych wejściowych, a nie kolejnością pierwszych słów.
Ręczne łączenie słów i pozostawienie spacji na początku lub końcu tekstu grupy.

Najczęstsze pytania4

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

W przypadku mapy mieszającej z kluczami utworzonymi z posortowanych liter tworzenie kluczy zajmuje O(n · k log k) dla n słów mających maksymalnie k liter, a operacje na mapie zajmują O(n · k). Ta wersja sortuje również słowa, aby uporządkować wynik, co dodaje O(n · k · log n). Wymagana pamięć to O(n · k) na klucze i grupy.

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

Klucz zliczeń, czyli 26 liczebności liter zapisanych jako tekst, na przykład 1#0#2#…, wymaga czasu O(k) zamiast O(k log k), więc sprawdza się lepiej w przypadku długich słów. W przypadku słów o długości najwyżej 8 liter sortowanie jest równie szybkie, a alfabetyczne sortowanie wyniku kosztuje więcej niż utworzenie któregokolwiek z kluczy. Oba klucze są poprawne, ponieważ dwa słowa mają takie same liczebności liter dokładnie wtedy, gdy mają takie same posortowane litery.

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

Różne litery mogą dać tę samą sumę: a + d jest równe b + c, więc ad i bc trafiłyby do jednej grupy. Klucz musi być taki sam dla anagramów i różny dla wszystkich pozostałych słów, a posortowane litery lub pełna liczba wystąpień każdej litery to gwarantują. Mnożenie jednej liczby pierwszej przypisanej do każdej litery również daje dokładny wynik, ale przy 101 dla z słowo składające się z dziesięciu liter z już powoduje przepełnienie 64-bitowej liczby całkowitej.

Dlaczego sortować dane wejściowe przed grupowaniem?

Odpowiedź wymaga posortowanych grup uporządkowanych według ich pierwszego słowa. Jednorazowe posortowanie wszystkich słów daje oba efekty: każda grupa otrzymuje swoje słowa w kolejności alfabetycznej, a grupa jest tworzona, gdy pojawia się jej pierwsze słowo. Posortowanie później każdej grupy, a następnie grup według ich pierwszego słowa, daje ten sam rezultat, ale wymaga więcej kodu.

Python

def groupAnagrams(strs):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

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