Sprawdza czy dwa słowa są anagramami – zawierają te same litery w różnej kolejności.
Anagram to słowo lub zdanie powstałe z innego przez przestawienie liter. Oba wyrazy składają się z tej samej puli znaków i mają tę samą długość.
Przykłady: adam ↔ dama, fraktal ↔ kartafl, słoma ↔ omasł.
Algorytm zliczania liter: tworzymy tablicę 26 liczników (po jednym dla każdej litery alfabetu). Iterując po pierwszym słowie zwiększamy odpowiednie liczniki, a iterując po drugim – zmniejszamy. Jeśli na końcu wszystkie liczniki są zerami, słowa są anagramami. Indeks dla litery wyliczamy przez kod_ASCII(litera) - kod_ASCII('a').
Założenie: słowa zawierają tylko małe litery alfabetu angielskiego. Dla polskich liter trzeba rozszerzyć tablicę.
Pamięciowa O(1) – tablica liczników ma stały rozmiar 26, niezależny od długości słów.
Alternatywa: posortować oba słowa i porównać – O(n log n). Wersja zliczająca jest szybsza i lepsza na maturę.
funkcja czy_anagram(a, b): jeżeli długość(a) ≠ długość(b): zwróć fałsz // tablica liczników dla 26 liter alfabetu litery ← tablica 26 zer // zliczamy litery: w 'a' dodajemy, w 'b' odejmujemy dla i od 0 do długość(a) - 1: litery[ascii(a[i]) - ascii('a')] ← litery[ascii(a[i]) - ascii('a')] + 1 litery[ascii(b[i]) - ascii('a')] ← litery[ascii(b[i]) - ascii('a')] - 1 // sprawdzamy czy wszystkie liczniki zerują się dla i od 0 do 25: jeżeli litery[i] ≠ 0: zwróć fałsz zwróć prawda
def czy_anagram(a, b):
if len(a) != len(b):
return False
litery = [0] * 26
for i in range(len(a)):
litery[ord(a[i]) - ord('a')] += 1
litery[ord(b[i]) - ord('a')] -= 1
for liczba in litery:
if liczba != 0:
return False
return True
# Przykład użycia
print(czy_anagram("adam", "dama"))
# Wynik: True
print(czy_anagram("kot", "pies"))
# Wynik: False
print(czy_anagram("listen", "silent"))
# Wynik: TrueO(n)O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: