Anagrammer og frekvenskart for tegn
Løs group-anagrams, valid-anagram og permutation-in-string med frekvensarrayer og hash-kart for O(n)-løsninger.
Anagrammer og frekvenskart for tegn er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er et anagram?
To strenger er anagrammer hvis de inneholder de samme tegnene med de samme frekvensene, men i en annen rekkefølge. 'listen' og 'silent' er anagrammer. Den enkleste kontrollen av korrekthet er å sortere begge strengene og sammenligne dem: O(n log n). For løsninger på O(n) kan du sammenligne frekvenstabeller for tegn. Anagramproblemer er en fast del av strengintervjuer fordi de tester flere teknikker: hashing, sortering og frekvensarrayer.
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')) # FalseFrekvensarray for små bokstaver
Når tegnsettet er begrenset (for eksempel bare små bokstaver fra a til z), kan en hashtabell erstattes med en frekvensarray med størrelse 26. Indeksering med ord(c) - ord('a') mapper 'a'→0, 'b'→1, ..., 'z'→25. Arrayer er i praksis raskere enn dict-objekter på grunn av bedre cache-lokalitet og fravær av hashing-overhead. Dette trikset brukes i valid-anagram-, anagram-permutation-in-string- og palindrome-permutation-problemer.
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')) # FalseGruppere anagrammer
Gruppér en liste med strenger slik at alle anagrammer ligger sammen. Den kanoniske løsningen på O(n×m log m) bruker den sorterte strengen som nøkkel i en hashtabell. Alle anagrammer gir samme sorterte nøkkel og havner derfor i samme bøtte. En variant på O(n×m) bruker en tuppel med tegnantall som nøkkel — den er tregere å beregne, men unngår sortering helt. Tilnærmingen med sortert nøkkel foretrekkes nesten alltid fordi den er tydeligere.
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']Anagramnøkkel med telle-tuppel
I varianten for anagramgruppering på O(n×m) representeres frekvensen til hver streng som en tuppel med 26 tellinger: tuple(freq_array). Dette unngår sortering, men krever O(26×n×m) arbeid for å bygge alle nøklene. Tuppler kan hashes i Python, noe som gjør dem til gyldige dict-nøkler. Denne varianten er verdt å nevne når intervjueren ber om «en vilkårlig løsning på O(n×m)» — den viser forståelse for ulike avveininger.
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']))K mest frekvente elementer
Finn de k mest frekvente elementene i et array. Counter + heap: bygg en frekvenstabell i O(n), og hent deretter ut de k største frekvensene ved hjelp av en min-heap med størrelse k eller Counter.most_common(k). En tilnærming med bøttesortering på O(n) oppretter bøtter indeksert etter frekvens (fra 0 til n) og samler elementene i omvendt frekvensrekkefølge — en elegant løsning når k er stort.
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]Frekvenstabell for permutasjon i streng
Avgjør om en hvilken som helst permutasjon av strengen p er en delstreng i s. Frekvenstabellen for et vindu med lengde |p| må være lik frekvenstabellen for p. Når vinduet flyttes, øker du tellingen for tegnet som kommer inn, og reduserer tellingen for tegnet som forlater vinduet. Det koster O(26) å sammenligne to Counter-objekter hver gang, noe som gir O(n×26) = O(n) totalt. Hold oversikt med «formed»-telleren for en likhetssjekk i 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')) # FalseMinste antall tegn for å lage et anagram
Gitt to strenger skal du finne det minste antallet tegn som må slettes for å gjøre den ene til et anagram av den andre. Beregn frekvenstabeller for begge strengene. Svaret er summen av de absolutte forskjellene i frekvensene. Tegn som finnes i den ene strengen, men ikke i den andre, må slettes i sin helhet. Denne løsningen på O(n) bruker mønsteret «merge and diff» på frekvenstabeller.
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')) # 5Frekvenstabell for løsepengebrev
Kontroller om alle tegnene i note kan skaffes fra tegnene i magazine (hvert tegn i magazine kan bare brukes én gang). Bygg en frekvenstabell over tegnene i magazine, og reduser deretter tellingen for hvert tegn i note. Hvis en telling blir negativ, returner False. Tidskompleksiteten er O(n + m), og plasskompleksiteten er O(1) for inndata med bare små bokstaver, når en array med 26 elementer brukes i stedet for en dict.
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')) # TrueHashing av anagrammer i delstrenger
For å kontrollere om to delstrenger i samme streng er anagrammer, kan du bruke en polynomisk hash av tegnfrekvenser som er kommutativ (uavhengig av rekkefølge). XOR av tegnverdier er kommutativt og kan oppdateres i O(1), men har høy sannsynlighet for kollisjoner. En bedre tilnærming bruker hashing med primtallsprodukter (hvert tegn mappes til et unikt primtall, og produktet er uavhengig av rekkefølgen). Dette er en nisjeteknikk for avanserte intervjuer.
# 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 matchSjekkliste for mønstre med frekvenstabeller
Gjenkjenn disse intervjumønstrene med frekvenstabeller:
- Gyldig anagram: samme lengde + samme frekvens → Counter-likhet eller arraysammenligning
- Gruppere anagrammer: sortert streng eller frekvenstuppel som dict-nøkkel
- K mest frekvente: Counter + heap eller bøttesortering
- Permutasjon i streng: glidende vindu + frekvenssammenligning
- Løsepengebrev: frekvenstabell for tilgjengelige tegn, reduser tellingen for behovet
- Palindrompermutasjon: høyst ett tegn med oddetallsfrekvens
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)) # 4Avvikeren: XOR for frekvenser
XOR er et kraftig verktøy for frekvensproblemer når nøyaktig ett element forekommer et oddetall ganger. XOR av et tall med seg selv kanselleres til 0: a XOR a = 0. XOR av alle elementene, der hver verdi forekommer et partall ganger bortsett fra én, etterlater bare den avvikende verdien. Dette gir tidskompleksitet O(n) og plasskompleksitet O(1) — ingen hashtabell er nødvendig. Teknikken kan generaliseres til å finne to verdier som forekommer et oddetall ganger, ved å bruke egenskapene til 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'Hurtigsjekk
Test forståelsen av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du at: frekvenstabeller for tegn er det viktigste verktøyet for å oppdage anagrammer — enten en array med 26 elementer for begrensede alfabeter eller en Counter for vilkårlige tegn, sorterte strenger eller dict-nøkler basert på frekvenstuppler grupperer alle anagrammer sammen på henholdsvis O(n × m log m) eller O(n × m), og XOR fjerner par på en effektiv måte i problemer med ett element som forekommer et oddetall ganger, og gir O(n) tid med O(1) plass når en dict ikke er nødvendig. Neste gang skal vi utforske strengkoding, reversering og palindromteknikker.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Anagrammer og frekvenskart for tegn» gratis?
Ja – hele teksten i «Anagrammer og frekvenskart for tegn» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Anagrammer og frekvenskart for tegn»?
Løs group-anagrams, valid-anagram og permutation-in-string med frekvensarrayer og hash-kart for O(n)-løsninger. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Anagrammer og frekvenskart for tegn»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Pythons streng-API for intervjuer
- Sliding window for delstrenger
- Anagrammer og frekvenskart for tegn
- Strengkoding, reversering og palindromer