Group Anagrams

Q: Apa kompleksitas waktu dari Group Anagrams?

Membuat kunci huruf yang diurutkan memerlukan O(n · k log k) untuk n kata dengan panjang hingga k huruf, dan pekerjaan pada map memerlukan O(n · k) . Mengurutkan kata-kata untuk mengurutkan output menambah O(n · k · log n) , yang menjadi faktor dominan. Ruang yang dibutuhkan adalah O(n · k) untuk kunci dan kelompok.

SedangHashing Pengurutan

+10

Kamu mendapatkan list kata strs. Dua kata merupakan anagram jika huruf-huruf pada salah satunya disusun ulang, dengan setiap huruf digunakan dalam jumlah yang sama. Kelompokkan setiap kata bersama semua anagramnya, lalu kembalikan satu string untuk setiap kelompok: kata-katanya diurutkan secara alfabetis dan dipisahkan dengan satu spasi. Urutkan kelompok secara alfabetis berdasarkan kata pertamanya.

Kata yang berulang dicantumkan dua kali dalam kelompoknya, sedangkan kata yang tidak memiliki anagram membentuk kelompok berisi satu kata. Urutan alfabetis berarti urutan seperti di kamus: aab berada sebelum ab, dan ab sebelum abc.

Fungsi

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

strsstring-array: kata-kata yang dikelompokkan, hanya huruf kecil
Mengembalikanstring-array: satu string per grup: kata-katanya diurutkan dan digabungkan dengan spasi, grup-grup diurutkan berdasarkan kata pertamanya

Batasan

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Setiap kata hanya berisi huruf bahasa Inggris kecil.

Contoh

Input: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Output: ["apple", "enlist listen silent", "notes onset stone tones"]
Penjelasan: enlist, listen, dan silent menggunakan e, i, l, n, s, dan t masing-masing satu kali. notes, onset, stone, dan tones memiliki e, n, o, s, dan t yang sama. apple tidak cocok dengan apa pun dan, sebagai kata pertama, menjadi yang terdepan.

Input: strs = ["race", "arc", "care", "car", "acre"]
Output: ["acre care race", "arc car"]
Penjelasan: acre, care, dan race memiliki huruf a, c, e, dan r yang sama. arc dan car tidak memiliki huruf e, jadi keduanya membentuk kelompok sendiri. acre muncul sebelum arc karena c muncul sebelum r pada huruf kedua.

Input: strs = ["b", "a", "b"]
Output: ["a", "b b"]
Penjelasan: Kedua salinan b adalah anagram satu sama lain, dan keduanya tetap berada dalam kelompok. a tidak memiliki pasangan dan berada di urutan pertama.

Pertanyaan lanjutan

Jika kata-kata dapat memuat karakter Unicode apa pun, kunci mana yang tetap berfungsi, huruf yang diurutkan atau jumlah huruf, dan apa yang akan kamu ubah di dalamnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Hitung kunci dari setiap kata secara terpisah yang sama untuk semua anagramnya dan berbeda untuk setiap kata lainnya. Huruf-huruf sebuah kata dalam urutan terurut menjadi kunci seperti itu, dan hash map dari kunci ke kelompok mengumpulkan kelompok-kelompok tersebut dalam satu kali proses. Urutkan kata-katanya terlebih dahulu agar urutan yang diperlukan terpenuhi dengan sendirinya.

Bandingkan setiap kata dengan setiap grup

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Simpan daftar grup dan bandingkan setiap kata dengan kata pertama dari setiap grup. Hubungan anagram bersifat transitif, jadi satu perbandingan per grup cukup untuk menentukan keanggotaan. Dua kata merupakan anagram jika panjangnya sama dan jumlah masing-masing dari 26 hurufnya sama. Urutkan input terlebih dahulu: setiap grup kemudian terisi menurut urutan alfabet, dan grup dibuat berdasarkan urutan kata pertamanya.

Jika tidak ada dua kata yang merupakan anagram, setiap kata harus diperiksa terhadap semua grup sebelumnya: 4000 kata menghasilkan sekitar 8 × 10^6 perbandingan, masing-masing memeriksa hingga 8 huruf dan 26 penghitung.

Algoritma

Urutkan kata-kata berdasarkan abjad.
Untuk setiap kata, cari grup yang kata pertamanya memiliki jumlah huruf yang sama, lalu tambahkan kata tersebut. Jika tidak ada yang cocok, mulai grup baru.
Kembalikan kata-kata di setiap grup yang digabungkan dengan spasi tunggal, sesuai urutan pembuatannya.

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]

Kelompokkan berdasarkan huruf yang sudah diurutkan dalam hash map

Intuisi

Hitung nama grup dari kata itu sendiri. Urutkan huruf-huruf dalam sebuah kata, dan setiap anagram menghasilkan teks yang sama: listen, silent, dan enlist semuanya menjadi eilnst, sedangkan stone menjadi enost. Dua kata memiliki bentuk terurut yang sama persis jika keduanya memiliki huruf yang sama dengan jumlah kemunculan yang sama, yang merupakan definisi anagram. Hash map dari kunci ke list kata kemudian mengelompokkan semuanya dalam satu kali lintasan, dan tidak ada kata yang dibandingkan dengan kata dari grup lain.

Urutannya berasal dari mengurutkan input terlebih dahulu, seperti sebelumnya: setiap list terisi secara alfabetis, dan sebuah kunci masuk ke map saat kata pertama dalam grupnya tiba. Map yang mempertahankan urutan penyisipan mengembalikan grup dalam urutan tersebut; jika tidak, simpan grup dalam list dan petakan setiap kunci ke indeksnya.

Mengurutkan input memerlukan sekitar 5 × 10^4 perbandingan kata untuk 4000 kata, bukan 8 × 10^6.

Algoritma

Urutkan kata-kata secara alfabetis.
Untuk setiap kata, buat kuncinya dengan mengurutkan huruf-hurufnya.
Cari kunci tersebut di hash map. Jika kunci itu baru, buat grup kosong untuk kunci tersebut dan pertahankan urutan grup saat dibuat.
Tambahkan kata ke grup untuk kuncinya.
Kembalikan kata-kata di setiap grup yang digabungkan dengan satu spasi, dengan urutan grup sesuai urutan pembuatannya.

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

Jebakan dan kasus tepi

Mengurutkan grup berdasarkan key, bukan berdasarkan kata pertama. Untuk ["cab", "bad"], key abc dan abd membuat cab berada di urutan pertama, tetapi bad seharusnya berada di urutan pertama.
Mengumpulkan kata dalam set. ["b", "a", "b"] harus menghasilkan b b; set hanya menyimpan satu salinan.
Membuat key hanya dari huruf-huruf yang berbeda. ab dan aabb menggunakan dua huruf yang sama, tetapi bukan anagram.
Mengurutkan setiap grup, tetapi tidak mengurutkan input maupun grup-grupnya. Urutan penyisipan pun mengikuti input, bukan kata pertama.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Group Anagrams?

Membuat kunci huruf yang diurutkan memerlukan O(n · k log k) untuk n kata dengan panjang hingga k huruf, dan pekerjaan pada map memerlukan O(n · k). Mengurutkan kata-kata untuk mengurutkan output menambah O(n · k · log n), yang menjadi faktor dominan. Ruang yang dibutuhkan adalah O(n · k) untuk kunci dan kelompok.

Apakah kunci jumlah huruf lebih cepat daripada mengurutkan setiap kata?

Kunci hitungan, yaitu 26 jumlah huruf yang ditulis sebagai teks seperti 1#0#2#…, membutuhkan O(k) alih-alih O(k log k), sehingga lebih unggul untuk kata-kata panjang. Untuk kata dengan 8 huruf atau kurang, pengurutan sama cepatnya. Kedua kunci ini akurat: dua kata memiliki jumlah huruf yang sama tepat ketika huruf-hurufnya memiliki urutan yang sama setelah diurutkan.

Mengapa tidak menggunakan jumlah kode huruf sebagai kunci?

Huruf yang berbeda dapat memiliki jumlah total yang sama: a + d sama dengan b + c, sehingga ad dan bc akan berada dalam grup yang sama. Hasil kali satu bilangan prima untuk setiap huruf bersifat tepat, tetapi jika z bernilai 101, kata yang terdiri dari sepuluh z akan melampaui kapasitas bilangan bulat 64-bit.

def groupAnagrams(strs):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

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