Group Anagrams

Q: Anagramları Gruplandırma işleminin zaman karmaşıklığı nedir?

Sıralanmış harf anahtarlarını oluşturmak, en fazla k harften oluşan n kelime için O(n · k log k) zaman alır ve harita işlemleri O(n · k) zaman alır. Çıktıyı sıralamak için kelimeleri sıralamak O(n · k · log n) ekler ve bu baskın maliyettir. Anahtarlar ve gruplar için alan kullanımı O(n · k) olur.

Q: Harf sayımı anahtarı, her kelimeyi sıralamaktan daha mı hızlıdır?

Sayı anahtarı, 1#0#2#… gibi metin olarak yazılmış 26 harf sayımı, O(k log k) yerine O(k) sürer; bu nedenle uzun sözcüklerde daha hızlıdır. 8 veya daha az harfte sıralama da aynı hızdadır. Her iki anahtar da kesindir: iki sözcüğün harf sayıları, sıralanmış harfleri aynıysa aynıdır.

OrtaHashing Sıralama

+10

Bir kelime listesi olan strs veriliyor. Bir kelime, diğerinin harfleri aynı sayıda kullanılarak yeniden düzenlendiğinde bu iki kelime anagramdır. Her kelimeyi tüm anagramlarıyla gruplayıp her grup için bir dize döndür: gruptaki kelimeleri alfabetik sırayla, tek boşluklarla birleştir. Grupları ilk kelimelerine göre alfabetik sırala.

Tekrarlanan bir kelime, grubunda iki kez listelenir; anagramı olmayan bir kelime ise tek elemanlı bir grup oluşturur. Alfabetik sıra, sözlük sırası anlamına gelir: aab, ab'den; ab ise abc'den önce gelir.

Fonksiyon

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

strsstring-array: gruplandırılacak kelimeler, yalnızca küçük harfler
Döndürürstring-array: her grup için bir dize: sözcükleri sıralanıp boşluklarla birleştirilmiş, gruplar ilk sözcüklerine göre sıralanmış

Kısıtlar

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Her sözcük yalnızca küçük İngilizce harflerden oluşur.

Örnekler

Girdi: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Çıktı: ["apple", "enlist listen silent", "notes onset stone tones"]
Açıklama: enlist, listen ve silent sözcüklerinin her biri e, i, l, n, s ve t harflerini birer kez kullanır. notes, onset, stone ve tones sözcüklerinin ortak harfleri e, n, o, s ve t'dir. apple hiçbir şeyle eşleşmez ve ilk sözcük olarak öne çıkar.

Girdi: strs = ["race", "arc", "care", "car", "acre"]
Çıktı: ["acre care race", "arc car"]
Açıklama: acre, care ve race a, c, e ve r harflerini paylaşır. arc ve car sözcüklerinde e yoktur, bu yüzden kendi gruplarını oluştururlar. acre, arc sözcüğünden önce gelir çünkü ikinci harfte c, r'den önce gelir.

Girdi: strs = ["b", "a", "b"]
Çıktı: ["a", "b b"]
Açıklama: b'nin iki kopyası birbirinin anagramıdır ve ikisi de grupta kalır. a'nın eşi yoktur ve ilk sırada gelir.

Ek soru

Kelimeler herhangi bir Unicode karakteri içerebilseydi, hangi anahtar (sıralanmış harfler veya harf sayıları) yine işe yarardı ve onda neyi değiştirirdin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her kelimenin tek başına, tüm anagramları için aynı ve diğer tüm kelimeler için farklı olan bir anahtarını hesaplayın. Bir kelimenin sıralanmış harfleri böyle bir anahtardır ve anahtardan gruba eşleme yapan bir hash map, tek geçişte grupları toplar. Kelimeleri önce sıralayın; böylece gerekli sıralama kendiliğinden sağlanır.

Her kelimeyi her grupla karşılaştır

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Grupların listesini tut ve her sözcüğü her grubun ilk sözcüğüyle karşılaştır. Anagram olma ilişkisi geçişli olduğundan, gruba üyeliği belirlemek için grup başına bir karşılaştırma yeterlidir. İki sözcük, uzunlukları aynıysa ve 26 harfin her birinden aynı sayıda içeriyorsa anagramdır. Önce girdiyi sırala: böylece her grup alfabetik sırayla doldurulur ve gruplar ilk sözcüklerine göre oluşturulur.

Hiçbir iki sözcük anagram değilse, her sözcük kendisinden önceki her grupla karşılaştırılır: 4000 sözcük yaklaşık 8 × 10^6 karşılaştırma yapar; her karşılaştırmada en fazla 8 harf ve 26 sayaç işlenir.

Algoritma

Kelimeleri alfabetik olarak sırala.
Her kelime için, ilk kelimesinin aynı harf sayılarına sahip olduğu bir grup bul ve kelimeyi gruba ekle. Eşleşen bir grup yoksa yeni bir grup oluştur.
Her grubun kelimelerini, oluşturulma sırasına göre, tek boşluklarla birleştirerek döndür.

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]

Sıralanmış harflere göre bir hash map'te gruplandırın

Sezgi

Grubun adını sözcüğün kendisinden hesapla. Bir sözcüğün harflerini sırala; her anagram aynı metni verir: listen, silent ve enlist sözcüklerinin tümü eilnst olurken, stone sözcüğü enost olur. İki sözcük, harfleri aynı sayıda içeriyorsa sıralanmış biçimleri de aynıdır; anagramın tanımı budur. Anahtardan sözcük listesine eşleme yapan bir hash map, tek geçişte her şeyi gruplandırır ve hiçbir sözcük başka bir grupla karşılaştırılmaz.

Sıralama, daha önce olduğu gibi, girdinin önceden sıralanmasından gelir: her liste alfabetik sırayla dolar ve bir grubun ilk sözcüğü geldiğinde anahtar map'e eklenir. Ekleme sırasını koruyan bir map, grupları bu sırayla döndürür; aksi takdirde grupları bir listede tut ve her anahtarı listedeki bir indeksle eşle.

Girdiyi sıralamak, 4000 sözcük için yaklaşık 5 × 10^4 sözcük karşılaştırmasına mal olur; bu sayı 8 × 10^6'dan azdır.

Algoritma

Kelimeleri alfabetik olarak sırala.
Her kelime için, harflerini sıralayarak anahtarını oluştur.
Anahtarı bir hash map'te ara. Yeni ise, oluşturduğun grupların sırasını koruyarak onun için boş bir grup başlat.
Kelimeyi anahtarının grubuna ekle.
Her grubun kelimelerini tek boşluklarla birleştirerek, grupları oluşturulma sırasıyla döndür.

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

Tuzaklar ve uç durumlar

Grupları ilk sözcüğe göre değil, anahtara göre sıralamak. ["cab", "bad"] için abc ve abd anahtarları cab sözcüğünü önce getirir, ancak önce bad gelmelidir.
Sözcükleri bir kümede toplamak. ["b", "a", "b"] için b b elde edilmelidir; küme tek kopya tutar.
Yalnızca farklı harflerden oluşan bir anahtar oluşturmak. ab ve aabb aynı iki harfi kullanır, ancak birbirinin anagramı değildir.
Her grubu sıralayıp girdiyi ve grupları sıralamamak. Bu durumda ekleme sırası ilk sözcüklere değil, girdiye bağlı olur.

Sıkça sorulan sorular3

Anagramları Gruplandırma işleminin zaman karmaşıklığı nedir?

Sıralanmış harf anahtarlarını oluşturmak, en fazla k harften oluşan n kelime için O(n · k log k) zaman alır ve harita işlemleri O(n · k) zaman alır. Çıktıyı sıralamak için kelimeleri sıralamak O(n · k · log n) ekler ve bu baskın maliyettir. Anahtarlar ve gruplar için alan kullanımı O(n · k) olur.

Harf sayımı anahtarı, her kelimeyi sıralamaktan daha mı hızlıdır?

Sayı anahtarı, 1#0#2#… gibi metin olarak yazılmış 26 harf sayımı, O(k log k) yerine O(k) sürer; bu nedenle uzun sözcüklerde daha hızlıdır. 8 veya daha az harfte sıralama da aynı hızdadır. Her iki anahtar da kesindir: iki sözcüğün harf sayıları, sıralanmış harfleri aynıysa aynıdır.

Harf kodlarının toplamını neden anahtar olarak kullanmıyoruz?

Farklı harflerin toplamı aynı olabilir: a + d, b + c'ye eşittir; bu nedenle ad ve bc aynı grupta yer alır. Her harf için bir asal sayının çarpımı kesin sonuç verir, ancak z için 101 kullanıldığında, on z'den oluşan bir sözcük 64 bitlik bir tamsayıyı aşar.

def groupAnagrams(strs):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı

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