DSA Interview Prep · Pelajaran

Anagram dan Peta Kekerapan Aksara

Selesaikan group-anagrams, valid-anagram dan permutation-in-string menggunakan tatasusunan kekerapan serta peta cincangan untuk penyelesaian O(n).

Pelajaran 3 daripada 413 langkah

Anagram dan Peta Kekerapan Aksara ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah Anagram?

Dua rentetan ialah anagram jika kedua-duanya mengandungi aksara yang sama dengan frekuensi yang sama, cuma dalam susunan yang berbeza. 'batu' dan 'tuba' ialah anagram. Semakan ketepatan paling mudah ialah mengisih kedua-dua rentetan dan membandingkannya: O(n log n). Untuk penyelesaian O(n), bandingkan peta frekuensi aksara. Masalah anagram sering muncul dalam temu duga rentetan kerana masalah ini menguji beberapa teknik: pencincangan, pengisihan dan tatasusunan frekuensi.

def is_anagram_sort(s, t):
    return sorted(s) == sorted(t)  # O(n log n)

def is_anagram_counter(s, t):
    from collections import Counter
    return Counter(s) == Counter(t)  # O(n)

def is_anagram_array(s, t):
    if len(s) != len(t): return False
    freq = [0] * 26
    for a, b in zip(s, t):
        freq[ord(a) - ord('a')] += 1
        freq[ord(b) - ord('a')] -= 1
    return all(f == 0 for f in freq)  # O(n)

print(is_anagram_array('anagram', 'nagaram'))  # True
print(is_anagram_array('rat', 'car'))           # False

Tatasusunan Frekuensi untuk Huruf Kecil

Apabila set aksara adalah terhad, contohnya hanya huruf kecil a-z, gantikan peta cincang dengan tatasusunan frekuensi bersaiz 26. Pengindeksan menggunakan ord(c) - ord('a') memetakan 'a'→0, 'b'→1, ..., 'z'→25. Dalam amalan, tatasusunan lebih pantas daripada kamus kerana kecekapan cache dan tiada kos tambahan pencincangan. Helah ini muncul dalam masalah anagram sah, permutasi anagram dalam rentetan dan permutasi palindrom.

def build_freq(s):
    freq = [0] * 26
    for c in s:
        freq[ord(c) - ord('a')] += 1
    return freq

def is_anagram_fast(s, t):
    return len(s) == len(t) and build_freq(s) == build_freq(t)

# Palindrome permutation: at most one odd-count character
def can_form_palindrome(s):
    freq = build_freq(s)
    odd_count = sum(1 for f in freq if f % 2 == 1)
    return odd_count <= 1

print(can_form_palindrome('carerace'))  # True ('racecar')
print(can_form_palindrome('hello'))     # False

Kumpulkan Anagram

Kumpulkan senarai rentetan supaya semua anagram muncul bersama. Penyelesaian O(n×m log m) yang lazim menggunakan rentetan terisih sebagai kunci peta cincang. Semua anagram menghasilkan kunci terisih yang sama, lalu diletakkan dalam kelompok yang sama. Variasi O(n×m) menggunakan tupel kiraan aksara sebagai kunci — lebih lambat untuk dikira tetapi tidak memerlukan pengisihan langsung. Pendekatan kunci terisih hampir sentiasa lebih disukai kerana lebih jelas.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # or ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

words = ['eat','tea','tan','ate','nat','bat']
result = group_anagrams(words)
for g in sorted(result, key=len, reverse=True):
    print(sorted(g))
# ['ate', 'eat', 'tea']
# ['nat', 'tan']
# ['bat']

Kunci Anagram dengan Tupel Kiraan

Untuk variasi pengumpulan anagram O(n×m), wakili frekuensi setiap rentetan sebagai tupel yang mengandungi 26 kiraan: tuple(freq_array). Cara ini mengelakkan pengisihan tetapi memerlukan kerja O(26×n×m) untuk membina semua kunci. Tupel boleh dicincang dalam Python, menjadikannya kunci kamus yang sah. Variasi ini wajar disebut apabila penemuduga meminta 'sebarang penyelesaian O(n×m)' — ini menunjukkan pemahaman tentang pertukaran antara pilihan yang berbeza.

from collections import defaultdict

def group_anagrams_count(strs):
    groups = defaultdict(list)
    for s in strs:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
        key = tuple(freq)  # tuple is hashable
        groups[key].append(s)
    return list(groups.values())

print(group_anagrams_count(['eat','tea','tan','ate','nat','bat']))

Unsur Paling Kerap bagi K Teratas

Cari k unsur paling kerap dalam tatasusunan. Pengira + timbunan: bina peta frekuensi dalam O(n), kemudian keluarkan k frekuensi terbesar menggunakan timbunan minimum bersaiz k atau Counter.most_common(k). Pendekatan pengisihan baldi O(n) mencipta baldi yang diindeks mengikut frekuensi (0 hingga n) dan mengumpulkan unsur dalam susunan frekuensi menurun — cara yang kemas apabila k besar.

from collections import Counter
import heapq

def top_k_frequent_heap(nums, k):
    freq = Counter(nums)
    return heapq.nlargest(k, freq, key=freq.get)

def top_k_frequent_bucket(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, cnt in freq.items():
        buckets[cnt].append(num)
    result = []
    for i in range(len(buckets)-1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k: break
    return result[:k]

print(top_k_frequent_heap([1,1,1,2,2,3], 2))   # [1, 2]
print(top_k_frequent_bucket([1,1,1,2,2,3], 2)) # [1, 2]

Peta Frekuensi untuk Permutasi dalam Rentetan

Tentukan sama ada sebarang permutasi rentetan p ialah subrentetan s. Peta frekuensi tetingkap sepanjang |p| mesti sama dengan peta frekuensi p. Apabila tetingkap bergerak, tambah kiraan aksara yang masuk dan kurangkan kiraan aksara yang keluar. Membandingkan dua objek pengira memerlukan O(26) setiap kali, lalu memberikan O(n×26) = O(n) secara keseluruhan. Jejaki pembilang 'formed' untuk semakan kesamaan dalam O(1).

def check_inclusion_fast(p, s):
    if len(p) > len(s): return False
    need = [0] * 26
    have = [0] * 26
    for c in p:
        need[ord(c)-ord('a')] += 1
    for i in range(len(p)):
        have[ord(s[i])-ord('a')] += 1
    if need == have: return True
    for i in range(len(p), len(s)):
        have[ord(s[i])-ord('a')]         += 1
        have[ord(s[i-len(p)])-ord('a')] -= 1
        if need == have: return True
    return False

print(check_inclusion_fast('ab', 'eidbaooo'))  # True
print(check_inclusion_fast('ab', 'eidboaoo'))  # False

Bilangan Minimum Aksara untuk Membentuk Anagram

Diberi dua rentetan, cari bilangan minimum pemadaman aksara untuk menjadikan salah satu rentetan sebagai anagram kepada rentetan yang lain. Kira peta frekuensi bagi kedua-dua rentetan; jawapannya ialah jumlah perbezaan mutlak frekuensi. Aksara yang hadir dalam satu rentetan tetapi tiada dalam rentetan yang lain semuanya mesti dipadamkan. Penyelesaian O(n) ini menggunakan corak gabung dan beza pada peta frekuensi.

from collections import Counter

def min_steps_to_anagram(s, t):
    freq_s = Counter(s)
    freq_t = Counter(t)
    steps = 0
    # For each unique char across both strings:
    all_chars = set(freq_s) | set(freq_t)
    for c in all_chars:
        steps += abs(freq_s.get(c, 0) - freq_t.get(c, 0))
    return steps

# Or more concisely:
def min_steps_counter(s, t):
    diff = Counter(s) - Counter(t)
    return sum(diff.values())

print(min_steps_to_anagram('leetcode', 'practice'))  # 5
print(min_steps_counter('leetcode', 'practice'))      # 5

Peta Frekuensi untuk Nota Tebusan

Semak sama ada semua aksara dalam note boleh dibekalkan oleh aksara dalam magazine (setiap aksara majalah hanya boleh digunakan sekali). Bina peta frekuensi aksara majalah; kemudian, bagi setiap aksara dalam nota, kurangkan kiraannya. Jika mana-mana kiraan menjadi negatif, tandakan kegagalan. Masa ialah O(n + m) dan ruang ialah O(1) untuk input yang terhad kepada huruf kecil, dengan menggunakan tatasusunan 26 unsur dan bukannya kamus.

def can_construct(note, magazine):
    freq = [0] * 26
    for c in magazine:
        freq[ord(c) - ord('a')] += 1
    for c in note:
        freq[ord(c) - ord('a')] -= 1
        if freq[ord(c) - ord('a')] < 0:
            return False  # insufficient supply
    return True

print(can_construct('aa', 'aab'))    # True
print(can_construct('aa', 'ab'))     # False
print(can_construct('bg', 'efjbdfbdgbjjbghiklgdch'))  # True

Pencincangan Subrentetan Anagram Terpanjang

Untuk menyemak sama ada dua subrentetan daripada rentetan yang sama ialah anagram, gunakan cincangan polinomial frekuensi aksara yang bersifat komutatif, iaitu tidak bergantung pada susunan. XOR bagi nilai aksara bersifat komutatif dan boleh dikemas kini dalam O(1), tetapi mempunyai kebarangkalian perlanggaran yang tinggi. Pendekatan yang lebih baik menggunakan pencincangan hasil darab nombor perdana, iaitu setiap aksara dipetakan kepada nombor perdana yang berbeza dan hasil darabnya tidak bergantung pada susunan. Ini ialah teknik khusus untuk temu duga lanjutan.

# Prime product hash: each char maps to a prime
PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,
          43,47,53,59,61,67,71,73,79,83,89,97,101]

def char_hash(s):
    h = 1
    for c in s:
        h *= PRIMES[ord(c) - ord('a')]
    return h

# Two windows with equal hash are likely anagrams
print(char_hash('listen'))  # same as:
print(char_hash('silent'))  # should match

Senarai Semak Corak Peta Frekuensi

Kenal pasti corak peta frekuensi ini dalam temu duga:

Anagram sah: panjang sama + frekuensi sama → kesamaan pengira atau perbandingan tatasusunan
Kumpulan anagram: rentetan terisih atau tupel frekuensi sebagai kunci kamus
Unsur paling kerap bagi k teratas: pengira + timbunan atau pengisihan baldi
Permutasi dalam rentetan: tetingkap gelongsor + perbandingan frekuensi
Nota tebusan: peta frekuensi bekalan, kurangkan untuk memenuhi permintaan
Permutasi palindrom: paling banyak satu aksara dengan kiraan ganjil

Semuanya berpunca daripada idea teras yang sama: frekuensi sebagai cap jari.

from collections import Counter

# Palindrome permutation
def palindrome_permutation(s):
    return sum(v % 2 for v in Counter(s).values()) <= 1

# First unique character
def first_unique(s):
    freq = Counter(s)
    for i, c in enumerate(s):
        if freq[c] == 1:
            return i
    return -1

# Character replacement for longest repeat
def char_replacement(s, k):
    freq = Counter()
    left = best = max_freq = 0
    for right, c in enumerate(s):
        freq[c] += 1
        max_freq = max(max_freq, freq[c])
        if (right - left + 1) - max_freq > k:
            freq[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print(palindrome_permutation('carerace'))  # True
print(first_unique('leetcode'))             # 0
print(char_replacement('AABABBA', 1))      # 4

Yang Berbeza: XOR untuk Frekuensi

XOR ialah alat yang berkuasa untuk masalah frekuensi apabila tepat satu unsur muncul dalam bilangan ganjil. XOR bagi nombor dengan dirinya sendiri terbatal menjadi 0: a XOR a = 0. XOR semua unsur, apabila setiap nilai muncul dalam bilangan genap kecuali satu, meninggalkan unsur yang muncul dalam bilangan ganjil itu sahaja. Ini memberikan masa O(n) dan ruang O(1) — peta cincang tidak diperlukan. Teknik ini boleh diperluas untuk mencari dua nombor yang muncul dalam bilangan ganjil menggunakan sifat XOR.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n  # XOR cancels pairs
    return result

print(single_number([4,1,2,1,2]))   # 4
print(single_number([2,2,1]))       # 1

# Find the unique character in an anagram check:
def find_difference(s, t):
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

print(find_difference('abcd', 'abcde'))  # 'e'

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Rumusan Pelajaran

Dalam pelajaran ini, anda mempelajari: peta frekuensi aksara ialah alat teras untuk mengesan anagram — sama ada tatasusunan 26 unsur bagi abjad terhad atau pengira bagi aksara sewenang-wenangnya, kunci kamus berupa rentetan terisih atau tupel frekuensi mengumpulkan semua anagram bersama dalam masa O(n × m log m) atau O(n × m), dan XOR menghapuskan pasangan dengan kemas bagi masalah unsur tunggal yang muncul dalam bilangan ganjil, memberikan masa O(n) dengan ruang O(1) apabila kamus tidak diperlukan. Seterusnya, kita akan meneroka pengekodan rentetan, pembalikan dan teknik palindrom.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 30
Pelajaran: 120

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Anagram dan Peta Kekerapan Aksara” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Anagram dan Peta Kekerapan Aksara”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Anagram dan Peta Kekerapan Aksara”?

Selesaikan group-anagrams, valid-anagram dan permutation-in-string menggunakan tatasusunan kekerapan serta peta cincangan untuk penyelesaian O(n). Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.

Berapa lamakah pelajaran “Anagram dan Peta Kekerapan Aksara” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

API Rentetan Python untuk Temu Duga
Tetingkap Gelangsar untuk Subrentetan
Anagram dan Peta Kekerapan Aksara
Pengekodan Rentetan, Pembalikan dan Palindrom

← Kembali ke DSA Interview Prep