Anagrammit ja merkkifrekvenssikartat
Ratkaiskaa group-anagrams-, valid-anagram- ja permutation-in-string-tehtävät frekvenssitaulukoilla ja hajautustauluilla O(n)-ajassa.
Anagrammit ja merkkifrekvenssikartat on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mikä on anagrammi
Kaksi merkkijonoa ovat anagrammeja, jos ne sisältävät samat merkit samoilla frekvensseillä, mutta eri järjestyksessä. 'listen' ja 'silent' ovat anagrammeja. Yksinkertaisin oikeellisuustarkistus on lajitella molemmat merkkijonot ja verrata niitä keskenään: O(n log n). O(n)-ratkaisuissa verrataan merkkien frekvenssikarttoja. Anagrammiongelmat ovat työhaastatteluissa yleisiä, koska ne testaavat useita tekniikoita: hajautusta, lajittelua ja frekvenssitaulukoita.
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')) # FalsePienaakkosten frekvenssitaulukko
Kun merkistö on rajattu, esimerkiksi vain pieniin a-z-kirjaimiin, korvaa hajautustaulu frekvenssitaulukolla, jonka koko on 26. Indeksointi lausekkeella ord(c) - ord('a') yhdistää merkin 'a' indeksiin 0, merkin 'b' indeksiin 1, ..., ja merkin 'z' indeksiin 25. Taulukot ovat käytännössä sanakirjoja nopeampia välimuistin paikallisuuden ja hajautuksen käsittelykulujen puuttumisen vuoksi. Tätä niksiä käytetään valid-anagram-, anagram-permutation-in-string- ja palindrome-permutation-ongelmissa.
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')) # FalseAnagrammien ryhmittely
Ryhmittele merkkijonojen lista niin, että kaikki anagrammit ovat yhdessä. Tavallisessa O(n×m log m) -ratkaisussa hajautustaulun avaimena käytetään lajiteltua merkkijonoa. Kaikki anagrammit tuottavat saman lajitellun avaimen, joten ne päätyvät samaan lokeroon. O(n×m)-muunnelmassa avaimena käytetään merkkien lukumääristä muodostettua tuplea — sen laskeminen on hitaampaa, mutta lajittelua ei tarvita lainkaan. Lajiteltuun avaimeen perustuva ratkaisu on lähes aina selkeytensä vuoksi suositeltava.
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']Anagrammiavain lukumäärätuplena
O(n×m)-aikavaativuuden anagrammien ryhmittelymuunnelmassa kunkin merkkijonon frekvenssi esitetään 26 lukumäärän tuplena: tuple(freq_array). Tämä välttää lajittelun, mutta kaikkien avainten muodostaminen vaatii O(26×n×m) työtä. Tuplet ovat Pythonissa hajautettavia, joten niitä voi käyttää dict-avaimina. Tämä muunnelma kannattaa mainita, kun haastattelija pyytää ”minkä tahansa O(n×m)-ratkaisun” — se osoittaa, että ymmärrät eri kompromissit.
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 yleisimmin esiintyvää alkiota
Etsi taulukon k yleisimmin esiintyvää alkiota. Counter + heap: muodosta frekvenssikartta O(n)-ajassa ja poimi sitten k suurinta frekvenssiä käyttämällä kooltaan k:n suuruista minimikekoa tai ilmaisua Counter.most_common(k). O(n)-aikainen lokerolajittelu muodostaa frekvenssin mukaan indeksoidut lokerot, joiden indeksit ovat välillä 0–n, ja kerää alkiot käänteisessä frekvenssijärjestyksessä — tämä on elegantti ratkaisu, kun k on suuri.
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]Merkkijonon permutaation frekvenssikartta
Määritä, esiintyykö jokin merkkijonon p permutaatio merkkijonossa s alimerkkijonona. Pituudeltaan |p| olevan ikkunan frekvenssikartan on oltava sama kuin p:n frekvenssikartan. Kun ikkuna liukuu, kasvata ikkunaan tulevan merkin lukumäärää ja pienennä ikkunasta poistuvan merkin lukumäärää. Kahden Counter-olion vertaaminen maksaa O(26) jokaisella kerralla, joten kokonaisaikavaativuus on O(n×26) = O(n). Seuraa formed-laskuria, jotta tasa-arvo voidaan tarkistaa O(1)-ajassa.
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')) # FalseAnagrammin muodostamiseen tarvittavien merkkien vähimmäismäärä
Kun annetaan kaksi merkkijonoa, etsi pienin merkkien poistojen määrä, jolla toinen voidaan muuttaa toisen anagrammiksi. Laske molempien merkkijonojen frekvenssikartat; vastaus on frekvenssien absoluuttisten erojen summa. Toisessa merkkijonossa esiintyvät mutta toisesta puuttuvat merkit on poistettava kokonaan. Tämä O(n)-ratkaisu käyttää frekvenssikarttojen ”merge and diff” -mallia.
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')) # 5Lunnasviestin frekvenssikartta
Tarkista, voidaanko kaikki note-merkkijonon merkit muodostaa magazine-merkkijonon merkeistä, kun kutakin magazine-merkkiä voi käyttää vain kerran. Muodosta magazine-merkkien frekvenssikartta ja vähennä sitten laskuria jokaisesta note-merkkijonon merkistä. Jos jokin laskuri muuttuu negatiiviseksi, palauta False. Aikavaativuus on O(n + m), ja pienaakkosiin rajoitetuilla syötteillä tilavaativuus on O(1), kun sanakirjan sijaan käytetään 26 alkion taulukkoa.
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')) # TruePisimpiin anagrammialimerkkijonoihin liittyvä hajautus
Jos haluat tarkistaa, ovatko saman merkkijonon kaksi alimerkkijonoa anagrammeja, käytä merkkien frekvensseistä laskettavaa polynomista hajautusarvoa, joka on vaihdannainen eli järjestyksestä riippumaton. Merkkien arvojen XOR on vaihdannainen ja päivitettävissä O(1)-ajassa, mutta törmäysten todennäköisyys on suuri. Parempi vaihtoehto on alkutulohajautus, jossa kukin merkki yhdistetään eri alkulukuun ja tulo on järjestyksestä riippumaton. Tämä on edistyneiden työhaastattelujen erikoistekniikka.
# 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 matchFrekvenssikarttojen mallien tarkistuslista
Tunnista nämä työhaastatteluissa yleiset frekvenssikarttamallit:
- Kelvollinen anagrammi: sama pituus + samat frekvenssit → Counter-tasa-arvo tai taulukoiden vertailu
- Anagrammien ryhmittely: lajiteltu merkkijono tai frekvenssituple dict-avaimena
- K yleisimmin esiintyvää: Counter + heap tai lokerolajittelu
- Permutaatio merkkijonossa: liukuva ikkuna + frekvenssien vertailu
- Lunnasviesti: lähteen frekvenssikartta, jota vähennetään tarpeen mukaan
- Palindromin permutaatio: enintään yksi parittoman frekvenssin merkki
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)) # 4Yksi poikkeava alkio: XOR frekvenssien käsittelyssä
XOR on tehokas työkalu frekvenssiongelmissa, kun täsmälleen yksi alkio esiintyy parittoman monta kertaa. Luvun XOR-operaatio itsensä kanssa kumoutuu nollaksi: a XOR a = 0. Kun kaikkien alkioiden XOR lasketaan ja jokainen arvo esiintyy parillisen monta kertaa yhtä lukuun ottamatta, tulokseksi jää ainoastaan parittomasti esiintyvä alkio. Tämä antaa O(n)-aikavaativuuden ja O(1)-tilavaativuuden ilman hajautustaulua. Menetelmää voi yleistää kahden parittomasti esiintyvän luvun etsimiseen XOR:n ominaisuuksien avulla.
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'Pikatesti
Testaa ymmärrystäsi oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opit, että merkkien frekvenssikartat ovat anagrammien tunnistamisen perustyökalu — rajatuilla aakkostoilla voidaan käyttää 26 alkion taulukkoa ja mielivaltaisilla merkeillä Counter-oliota, lajitellut merkkijonot tai frekvenssituplet dict-avaimina ryhmittelevät kaikki anagrammit yhteen O(n × m log m)- tai vastaavasti O(n × m)-ajassa ja XOR kumoaa parit tehokkaasti yhden parittomasti esiintyvän alkion ongelmissa, jolloin aikavaativuus on O(n) ja tilavaativuus O(1), kun sanakirjaa ei tarvita. Seuraavaksi tutustumme merkkijonojen koodaukseen, kääntämiseen ja palindromitekniikoihin.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Anagrammit ja merkkifrekvenssikartat” ilmainen?
Kyllä – oppitunnin ”Anagrammit ja merkkifrekvenssikartat” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Anagrammit ja merkkifrekvenssikartat”?
Ratkaiskaa group-anagrams-, valid-anagram- ja permutation-in-string-tehtävät frekvenssitaulukoilla ja hajautustauluilla O(n)-ajassa. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Anagrammit ja merkkifrekvenssikartat”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Pythonin merkkijono-API haastattelutehtäviin
- Liukuva ikkuna alimerkkijonoille
- Anagrammit ja merkkifrekvenssikartat
- Merkkijonojen koodaus, kääntäminen ja palindromit