Group Anagrams

Q: Harf sayılarını tutan bir 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ından oluşur ve O(k log k) yerine O(k) zaman alır; bu nedenle uzun kelimelerde daha hızlıdır. En fazla 8 harfli kelimelerde sıralama da aynı hızdadır ve çıktının alfabetik sıralanması, her iki anahtardan da daha fazla maliyet getirir. Her iki anahtar da doğrudur; çünkü iki kelimenin harf sayımları, yalnızca sıralanmış harfleri aynı olduğunda aynıdır.

OrtaHashing Sıralama

+10

Bir strs sözcük listesi alırsın. İki sözcük, biri diğerinin yeniden düzenlenmiş hâliyse, yani aynı harfleri aynı sayıda içeriyorsa anagramdır. Her sözcüğü tüm anagramlarıyla birlikte bir gruba koy ve her grup için bir dize döndür: gruptaki sözcükler alfabetik sırada, aralarında tek boşluk olacak şekilde birleştirilir. Grupları ilk sözcüklerine göre alfabetik olarak sırala.

İki kez geçen bir sözcük, grubunda iki kez listelenir; anagramı olmayan bir sözcük ise tek üyeli bir grup oluşturur. Alfabetik sıra sözlük sırası demektir: aab, ab'den; ab ise abc'den önce gelir.

Fonksiyon

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

strsstring-array: gruplandırılacak sözcükler, 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 harfler içerir.

Ö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ükleri e, n, o, s ve t harflerini paylaşır; apple ise hiçbir eşleşme bulmaz. İlk sözcüğe göre gruplar apple, enlist, notes sırasındadır.

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 içinde e harfi yoktur, bu yüzden kendi gruplarını oluştururlar. acre, arc'den ö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 başta gelir.

Gönderirken +15 gizli test

Ek soru

Words öğelerinin 26 küçük harf yerine herhangi bir Unicode karakterini içerebildiğini varsayalım. İki anahtardan hangisi — sıralanmış harfler mi yoksa harf sayıları mı — hâlâ işe yarar 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 kelimeyi diğer her kelimeyle karşılaştırmak işe yarar, ancak her çift için tam bir karşılaştırma yapar. Bu sorunu çözen şey kanonik bir anahtardır: tek bir kelimeden hesapladığın, tüm anagramları için aynı ve diğer tüm kelimeler için farklı olan bir değer. Harfleri sıralanmış bir kelime böyle bir anahtardır; anahtardan gruba eşleme yapan bir hash tablosu da gruplamayı tek geçişte tamamlar. Kelimeleri gruplamadan önce sıralarsan istenen sıralama kendiliğinden elde edilir.

Her sözcüğü her grupla karşılaştırın

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

Sezgi

Anagram olma geçişlidir: stone, notes ile eşleşiyorsa ve notes, tones ile eşleşiyorsa, stone da tones ile eşleşir. Bu nedenle yeni bir sözcüğün grubun her üyesiyle eşleşmesi gerekmez. Gruba ait olup olmadığına, grubun ilk sözcüğüyle karşılaştırılarak karar verilir.

İki sözcüğü karşılaştırmak için harfleri sayın. Uzunlukları aynıysa ve her harf birinde diğerindeki kadar geçiyorsa bunlar anagramdır. İlk sözcüğün her harfi için 1 ekleyin ve ikinci sözcüğün her harfi için 1 çıkarın; ardından 26 sayacın tamamının 0 olduğunu kontrol edin.

Önce girdiyi sıralayın; böylece sıralama kendiliğinden sağlanır. Sözcükler alfabetik sırayla gelir ve her biri grubunun sonuna eklenir; bu nedenle tüm gruplar sıralı kalır. Bir grup, alfabetik olarak ilk sözcüğü geldiğinde oluşturulur; dolayısıyla gruplar ilk sözcüklerine göre zaten sıralıdır.

Maliyet, taramadan kaynaklanır. 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 4000 × 3999 / 2 ≈ 8 × 10^6 karşılaştırma demektir ve her karşılaştırmada 8 harfe ve 26 sayaca kadar işlem yapılır. Bu, en büyük testlerde Python, Lua ve R için çok yavaştır; ayrıca işlem miktarı listenin karesiyle büyür, bu nedenle 10^5 sözcükte herhangi bir dili zorlar.

Algoritma

Kelimeleri alfabetik sıraya göre sıralayın.
Her biri bir kelime listesinden oluşan grupların listesini tutun.
Her kelime için, ilk kelimesi aynı harf sayılarına sahip olan bir grup arayın ve kelimeyi bu gruba ekleyin.
Eşleşen grup yoksa yalnızca bu kelimeyi içeren yeni bir grup oluşturun.
Her grubun kelimelerini tek boşluklarla birleştirin ve grupları oluşturduğunuz sırayla döndürün.

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]

Harfleri sıralayarak bir hash map'te gruplayın

Sezgi

Bir sözcüğün hangi gruba uyduğunu sormak yerine, grubun adını sözcüğün kendisinden hesaplayın. Bir sözcüğün harflerini sıralayın; tüm anagramları aynı metni verir: listen, silent ve enlist sözcüklerinin tümü eilnst olurken, stone sözcüğü enost olur. İki sözcük, ancak aynı harfleri aynı sayıda içeriyorsa sıralanmış biçimleri aynıdır; anagramın tanımı da budur. Bu nedenle sıralanmış biçim, grup için kanonik bir anahtardır.

Anahtardan sözcük listesine eşleme yapan bir hash map, tek geçişte her şeyi gruplandırır. Her sözcük için en fazla 8 harfi sıralamak ve harita üzerinde bir arama yapmak gerekir; sözcük hiçbir zaman başka bir grupla karşılaştırılmaz.

Sıralamayı korumak için ilk yaklaşımda olduğu gibi gruplandırmadan önce girdiyi sıralayın. Sözcükler alfabetik sırayla gelir, bu yüzden her liste sırayla dolar ve bir anahtar, grubunun ilk sözcüğü geldiğinde haritaya eklenir. Ekleme sırasını koruyan haritalar (Python dict, JavaScript Map, Java LinkedHashMap, Dart map, Ruby hash'leri ve PHP dizileri) grupları bu sırayla döndürür. Haritanın sırası yoksa her grubun indeksini haritada, grupların kendisini de bir listede saklayın.

Girdiyi sıralamak, en fazla k harfi içeren yaklaşık n log n karşılaştırma alır; 4000 sözcük için bu, 8 × 10^6 yerine yaklaşık 5 × 10^4 sözcük karşılaştırması demektir. Anahtarları oluşturmak O(n · k log k) maliyet ekler; k ≤ 8 olduğundan bu, sıralama maliyetinin yanında küçüktür.

Algoritma

Kelimeleri alfabetik olarak sırala.
Her kelime için harflerini sıralayarak anahtarını oluştur.
Anahtarı bir karma eşlemede ara. Yeni bir anahtarsa, grupları oluşturduğun sırayı 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ına göre 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

Gruplama, insanların alıştırma yaptığı kısımdır. Bu sürümdeki yanlış yanıtların çoğu çıktı sıralamasından ve benzersiz olmayan anahtarlardan kaynaklanır.

Grupları ilk sözcüklerine göre değil, anahtarlarına göre sıralamak. Anahtar, sözcüklerinin en küçük yeniden düzenlenmiş hâlidir; sözcüklerden biri değildir: ["cab", "bad"] için anahtarlar abc ve abd olur; bu, cab sözcüğünü önceye koyardı, ancak ilk sözcüğe göre sıralandığında bad önce gelir.
Sözcükleri bir kümede toplamak. ["b", "a", "b"] girdisi b b sonucunu vermelidir; küme yalnızca bir kopya tutar.
Yalnızca farklı harflerden oluşturulan bir anahtar. ab ve aabb aynı iki harfi kullanır, ancak aabb her harften iki tane içerir; bu nedenle bunlar anagram değildir.
Harf kodlarını toplayan bir anahtar. ad ve bc aynı toplama sahiptir; bu nedenle toplama, hiçbir ortak harfi olmayan sözcükleri birleştirir.
Her grubu sıralayıp girdiyi sıralamamak, ardından grupları sıralamayı unutmak. Böylece ekleme sırası, ilk sözcüklerin sırası değil, girdinin sırası olur.
Elle birleştirip bir grubun metninin başında veya sonunda boşluk bırakmak.

Sıkça sorulan sorular4

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

Sıralanmış harflerle anahtarlanan bir hash map kullanıldığında, en fazla k harften oluşan n kelime için anahtarları oluşturmak O(n · k log k) sürer ve map işlemleri O(n · k) sürer. Bu sürüm ayrıca çıktıyı sıralamak için kelimeleri de sıralar; bu da O(n · k · log n) ekler. Anahtarlar ve gruplar için gereken alan O(n · k) kadardır.

Harf sayılarını tutan bir 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ından oluşur ve O(k log k) yerine O(k) zaman alır; bu nedenle uzun kelimelerde daha hızlıdır. En fazla 8 harfli kelimelerde sıralama da aynı hızdadır ve çıktının alfabetik sıralanması, her iki anahtardan da daha fazla maliyet getirir. Her iki anahtar da doğrudur; çünkü iki kelimenin harf sayımları, yalnızca sıralanmış harfleri aynı olduğunda aynıdır.

Anahtar olarak neden harf kodlarının toplamını kullanmıyoruz?

Farklı harfler aynı toplamı verebilir: a + d, b + c'ye eşittir; bu nedenle ad ve bc aynı gruba düşer. Anagramlar için anahtarlar eşit, diğer her şey için farklı olmalıdır; sıralanmış harfler veya her harfin tam sayımı bunu garanti eder. Her harf için bir asal sayıyı çarpmak da kesin sonuç verir, ancak z için 101 kullanıldığında, on z'den oluşan bir sözcük bile 64 bitlik bir tamsayıda taşmaya neden olur.

Gruplamadan önce girdi neden sıralanır?

Yanıt, ilk sözcüklerine göre sıralanmış gruplar istiyor. Tüm sözcükleri bir kez sıralamak ikisini de sağlar: her grup sözcüklerini alfabetik sırayla alır ve ilk sözcüğü geldiğinde bir grup oluşturulur. Sonrasında her grubu, ardından grupları ilk sözcüklerine göre sıralamak daha fazla kodla aynı sonucu verir.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

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