Tarkibga o'tish

Anagram guruhlari

So'zlar ro'yxati berilgan. Bir-birining anagrammasi bo'lgan so'zlarni bir guruhga to'plang. Har bir guruh anagramlar to'plami. Guruhlar tartibi va guruh ichidagi tartib muhim emas.

Kirish:  ["eat", "tea", "tan", "ate", "nat", "bat"]

Chiqish: [
           ["bat"],
           ["nat", "tan"],
           ["ate", "eat", "tea"]
         ]

"eat", "tea", "ate" — bir-birining anagrammasi. "tan", "nat" — yana bir anagramma juftligi. "bat" boshqa hech biri bilan anagramma emas, u yolg'iz guruh.

Asosiy g'oya: imzo (signature)

Bir xil anagrammalar bir xil harflardan tashkil topgan. Ular o'rtasida umumiy nima bor? Umumiy harf to'plami — imzo (signature yoki canonical form).

Imzo shunday tuzilishi kerakki: anagrammalar uchun bir xil, anagramma bo'lmaganlar uchun boshqacha bo'lsin.

Ikki asosiy imzo usuli:

  1. Saralangan harf ketma-ketligi: "eat" → "aet", "tea" → "aet", "ate" → "aet" — hammasi teng.
  2. Harf chastotasi vektori: "eat" → {a:1, e:1, t:1} — bir xil belgi oladi.

Imzo guruhlash kalitiga aylanadi: imzo → bu imzoga ega so'zlar ro'yxati.

Yondashuv: saralangan imzo

Har so'zni saralaymiz — bu so'zning imzosi. So'zni imzo kalit ostida mapga qo'shamiz.

FUNCTION GROUP_ANAGRAMS(words)
    groups = bo'sh hash map   // imzo → so'zlar ro'yxati

    FOR har bir word words ichida
        key = sorted(word)    // imzo

        IF groups CONTAINS key
            groups[key] ga word qo'sh
        ELSE
            groups[key] = [word] bilan yangi ro'yxat yarat

    RETURN groups'dagi barcha qiymatlar (ro'yxatlar)

Bosqichma-bosqich dry run

["eat", "tea", "tan", "ate", "nat", "bat"]:

groups = {}

word = "eat"
    key = sorted("eat") = "aet"
    "aet" yo'q → groups["aet"] = ["eat"]
    groups: {"aet": ["eat"]}

word = "tea"
    key = sorted("tea") = "aet"
    "aet" bor → groups["aet"] ga "tea" qo'sh
    groups: {"aet": ["eat", "tea"]}

word = "tan"
    key = sorted("tan") = "ant"
    "ant" yo'q → groups["ant"] = ["tan"]
    groups: {"aet": ["eat", "tea"], "ant": ["tan"]}

word = "ate"
    key = sorted("ate") = "aet"
    "aet" bor → groups["aet"] ga "ate" qo'sh
    groups: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

word = "nat"
    key = sorted("nat") = "ant"
    "ant" bor → groups["ant"] ga "nat" qo'sh
    groups: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

word = "bat"
    key = sorted("bat") = "abt"
    "abt" yo'q → groups["abt"] = ["bat"]
    groups: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

Natija ro'yxatlari:
    [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Chastota vektori imzosi

Saralangan harf o'rniga harf chastotasini imzo qilish mumkin. Bu O(k) vaqt beradi — k harf soni, O(n log n) saralash o'rniga.

Faqat a–z harflari bo'lganda 26 ta katakli massivni imzo sifatida ishlatish mumkin. Lekin massiv to'g'ridan-to'g'ri map kaliti bo'la olmaydi — uning matnga aylantirilgan ko'rinishi ishlatiladi.

FUNCTION GET_SIGNATURE(word)
    counts = 26 ta noldan iborat massiv

    FOR har bir char word ichida
        counts[char - 'a'] += 1

    RETURN counts'ni matn ko'rinishiga aylantir
    // masalan: "1#0#1#0#...#1#..." — chastotalarni ajratuvchi bilan birlashtirish

Chastota vektori imzosi "eat", "tea", "ate" uchun bir xil matn beradi.

"eat"  →  a:1, e:1, t:1  →  "0#0#0#0#1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0"
"tea"  →  a:1, e:1, t:1  →  aynan bir xil matn
"bat"  →  a:1, b:1, t:1  →  boshqacha matn

Qaysi imzo usulini tanlash masalaga bog'liq:

  • Saralangan harf: kodni tushunish oson, vaqt O(n * k log k).
  • Chastota vektori: vaqt O(n * k), lekin kodni qo'shimcha harakat talab qiladi.

k — so'z uzunligi, n — so'zlar soni.

Vaqt va xotira murakkabligi

Saralangan imzo yondashuvi:

  • Har so'zni saralash: O(k log k), n ta so'z uchun O(n * k log k).
  • Hash map amallar: kutiladigan O(1) har so'z uchun.
  • Jami vaqt: O(n * k log k), bu yerda n — so'zlar soni, k — o'rtacha so'z uzunligi.

Chastota vektori imzosi:

  • Har so'z uchun imzo hisoblash: O(k).
  • Jami vaqt: O(n * k).

Xotira:

  • n ta so'z mapda saqlanadi: O(n * k) — barcha so'z belgilarining jami.
  • Guruhlar natijasi ham O(n * k) xotira oladi.

Edge case'lar

Bitta so'z. ["abc"] → {"abc": ["abc"]} → [["abc"]]. To'g'ri: bitta so'z alohida guruh.

Barcha so'zlar bir-birining anagrammasi. ["eat", "tea", "ate"] → bitta guruhga tushadi.

Hech biri anagramma emas. ["abc", "def", "ghi"] → har biri alohida guruh.

Bo'sh satr. [""] → imzo bo'sh satr, bir guruhda.

Bir xil so'zlar. ["ab", "ab"] — ikkisi ham bir xil imzoga ega, bir guruhga tushadi: [["ab", "ab"]].

Bitta harf. ["a", "b", "a"] → {"a": ["a", "a"], "b": ["b"]}.

Note

Chastota vektori imzosi ajratuvchi belgisi tanloviga e'tibor talab qiladi. Masalan, harf chastotalari oddiy raqam birlashtirish bilan yozilsa: "12" va "21" — ular biri ikkinchisining anagrammasi bo'lmasin, lekin ayni matn hosil qilinishi mumkin. Aniq ajratuvchi — masalan, # — bu aralashuvni oldini oladi.

Algoritm to'g'riligini tekshirish

Saralangan imzo usuli uchun:

  • Anagrammalar har doim bir xil saralangan shaklga keladi: to'g'ri.
  • Anagramma bo'lmaganlar turli shaklga keladi: saralangan shakllar teng bo'lsa, ularda bir xil harflar bir xil miqdorda → ular anagramma.

Xulosa: saralangan imzo anagrammani aniqlash uchun zarur va yetarli shart.

Chastota vektori imzosi uchun ham xuddi shunday. Imzo bir xil → bir xil harf chastotalari → anagramma.

Masalaning variantlari

Juftlar soni. Guruhlash o'rniga faqat anagramma juftliklar soni so'ralsa, guruh hajmidan C(n, 2) = n*(n-1)/2 juft hisoblash mumkin.

Satrda faqat anagrammalarni o'chirish. Agar anagramma guruhi hajmi 1 bo'lsa, o'sha so'z anagrammasi yo'q — chiqariladi.

So'zlar emas, raqamlar. Raqamlar satrga aylantirilib, xuddi shu yondashuv ishlatilishi mumkin.

Dictionarydan faqat anagrammalar. Katta lug'atdan qidiriladigan so'zning barcha anagrammalarini topish: lug'at so'zlari guruhlanadi, kerakli so'z imzosi bilan guruh topiladi.

Xulosa

Anagram guruhlari masalasi hashlashning "guruhlash" shablonini ko'rsatadi. Har so'z uchun anagrammalarni birlashtiruvchi imzo hisoblanadi; imzo mapda kalit sifatida ishlatiladi.

Ikki imzo usuli — saralangan harf va chastota vektori — ikkalasi ham to'g'ri ishlaydi. Tanlov amalga oshirish qulayligiga va k ning katta-kichikligiga bog'liq.

Guruhlash shablon — kalit bo'lib xizmat qiladigan imzoni hisoblash va imzo → ro'yxat mapini qurish — anagrammalar uchun ham, boshqa "bir xil xususiyatli elementlarni to'plash" masalalarida ham qo'llanadi.