To'g'ri anagramma

Ikkita so'z berilgan. Ular bir-birining anagrammasi ekanligini aniqlang.

Anagramma — bir so'zdagi barcha harflarni qayta tartiblab, boshqa so'z hosil qilingan holat. Ikkala so'z bir xil harflardan, bir xil miqdorda iborat bo'ladi, faqat tartibi boshqacha.

"listen" va "silent"   → anagramma   (l,i,s,t,e,n — har ikkisida bir xil)
"anagram" va "nagaram" → anagramma
"rat" va "car"         → anagramma emas   (r,a,t va c,a,r — c va t farqli)
"hello" va "world"     → anagramma emas
"a" va "a"             → anagramma   (bir xil harf)
"ab" va "ba"           → anagramma

Birinchi yondashuv: saralash

Agar ikkala so'zni saralasak, anagrammalar bir xil saralangan shaklga keladi:

"listen"  →  sarala  →  "eilnst"
"silent"  →  sarala  →  "eilnst"

Saralangan shakl teng → anagramma

FUNCTION IS_ANAGRAM_SORT(s, t)
    IF uzunlik(s) ≠ uzunlik(t)
        RETURN FALSE

    RETURN sorted(s) = sorted(t)

Uzunliklarni avval tekshirish muhim: har xil uzunlikdagi so'zlar anagramma bo'la olmaydi va keraksiz saralashdan qochiladi.

Vaqt: O(n log n) (saralash), xotira: O(n) (saralangan nusxa). Bu to'g'ri yechim, lekin chiziqli vaqtda qilish mumkin.

Ikkinchi yondashuv: harf chastotasini hisoblash

Anagrammada ikkala so'zdagi har harf bir xil miqdorda bo'ladi. Shuning uchun har harfning chastotasini solishtirish yetarli.

Birinchi so'zdagi har harf uchun +1, ikkinchi so'zdagi har harf uchun -1 qilinsa, anagrammada barcha hisoblagichlar nolga qaytadi.

FUNCTION IS_ANAGRAM(s, t)
    IF uzunlik(s) ≠ uzunlik(t)
        RETURN FALSE

    counts = bo'sh hash map

    FOR har bir char s ichida
        counts[char] = counts[char] + 1   // mavjud bo'lmasa 0 dan boshlaydi

    FOR har bir char t ichida
        counts[char] = counts[char] - 1

    FOR har bir count counts ichida
        IF count ≠ 0
            RETURN FALSE

    RETURN TRUE

Yoki soddaroq: t ichidagi harf kamaytirilganda 0 dan pastga tushsa, anagramma emas:

FUNCTION IS_ANAGRAM_EARLY(s, t)
    IF uzunlik(s) ≠ uzunlik(t)
        RETURN FALSE

    counts = bo'sh hash map

    FOR har bir char s ichida
        counts[char] = counts[char] + 1

    FOR har bir char t ichida
        counts[char] = counts[char] - 1
        IF counts[char] < 0
            RETURN FALSE

    RETURN TRUE

Ikkinchi tsikl davomida biror harf hisoblagichi manfiy bo'lsa, tda shu harf sdan ko'proq — anagramma emas.

Bosqichma-bosqich dry run

s = "anagram", t = "nagaram":

Birinchi tsikl — s bo'yicha:

a: +1   counts: {a:1}
n: +1   counts: {a:1, n:1}
a: +1   counts: {a:2, n:1}
g: +1   counts: {a:2, n:1, g:1}
r: +1   counts: {a:2, n:1, g:1, r:1}
a: +1   counts: {a:3, n:1, g:1, r:1}
m: +1   counts: {a:3, n:1, g:1, r:1, m:1}

Ikkinchi tsikl — t bo'yicha:

n: -1   counts: {a:3, n:0, g:1, r:1, m:1}
a: -1   counts: {a:2, n:0, g:1, r:1, m:1}
g: -1   counts: {a:2, n:0, g:0, r:1, m:1}
a: -1   counts: {a:1, n:0, g:0, r:1, m:1}
r: -1   counts: {a:1, n:0, g:0, r:0, m:1}
a: -1   counts: {a:0, n:0, g:0, r:0, m:1}
m: -1   counts: {a:0, n:0, g:0, r:0, m:0}

Barcha hisoblagichlar nol → RETURN TRUE

s = "rat", t = "car":

Birinchi tsikl: counts: {r:1, a:1, t:1}

Ikkinchi tsikl:

c: -1   counts: {r:1, a:1, t:1, c:-1}
         c manfiy → RETURN FALSE

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira	Eslatma
Saralash	`O(n log n)`	`O(n)`	Oddiy, universal
Harf chastotasi	`O(n)`	`O(k)`	k — noyob harf soni

Harf chastotasi yondashuvida k — alfavit hajmi. Faqat kichik lotin harflari bo'lsa, k = 26 — doimiy. Shuning uchun xotira murakkabligi O(1) deyilishi mumkin. Unicode yoki katta alfavit uchun k kattalashadi.

Vaqt murakkabligi O(n): ikkala so'z bir marta o'qiladi.

Edge case'lar

Har xil uzunliklar. "abc" va "ab" — uzunliklari teng emas, darhol FALSE. Bu tekshiruvni tushirib qoldirish noto'g'ri natijaga olib kelmaydi (harf hisobi nolda qolmaydi), lekin keraksiz ishni bajaradi.

Bir xil so'z. "abc" va "abc" — barcha hisoblagichlar qo'shiladi va ayiriladi, nolda qoladi → TRUE. To'g'ri: so'z o'zining anagrammasi.

Bitta harf. "a" va "a" → TRUE. "a" va "b" → FALSE.

Bo'sh satrlar. "" va "" → uzunliklari teng (0), hisoblagich bo'sh, barcha qiymatlar nol → TRUE. Mantiqan to'g'ri: bo'sh so'z o'zining anagrammasi.

Katta-kichik harf. Masala odatda harflar katta-kichikligiga sezgir bo'lmaydi deyilmasa, "Listen" va "Silent" anagramma hisoblanmaydi, chunki L va l turli kalit. Agar katta-kichik harfni bir xil ko'rish kerak bo'lsa, so'zlarni oldindan bir xil registrga o'girish kerak.

Bo'shliq va boshqa belgilar. Masala satrda faqat harf bo'lishini kafolatlamasa, " ", "." kabi belgilar ham hisobga olinadi.

Note

Masala shartnomasi aniq aytmasa, "faqat kichik lotin harflari" yoki "unicode belgilar" ekanini so'rash muhim. Bu xotira murakkabligini va kalit turini belgilaydi.

Faqat lotin harflari bo'lsa: massiv bilan optimallashtirish

Faqat a–z harflari bo'lsa, hash map o'rniga 26 ta katakli massiv ishlatilishi mumkin:

counts = 26 ta noldan iborat massiv

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

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

FOR har bir count ichida
    IF count ≠ 0
        RETURN FALSE

RETURN TRUE

char - 'a' alifbo tartibidagi offset'ni beradi: 'a' → 0, 'b' → 1, ..., 'z' → 25.

Bu yondashuv O(n) vaqt va O(1) xotira beradi, chunki massiv hajmi doim 26.

Xulosa

To'g'ri anagramma masalasi harf chastotasini hisoblash shablonini ko'rsatadi. Saralash O(n log n) vaqt bilan sodda ishlaydi. Hash map yordamida chastota hisoblash O(n) vaqt beradi; alfavit cheklangan bo'lsa, massiv O(1) xotira bilan yanada samaraliroq.

Chastota hisoblash — anagram guruhlarini topish, permutatsiya tekshirish va "bir so'zdan ikkinchisiga bir almashtirish bilan o'tish mumkinmi?" kabi masalalar uchun ham asosiy qurilish bloki.