Sprawdza, czy dwa słowa mają te same litery – przez liczenie ich wystąpień.
Anagram to słowo powstałe przez przestawienie liter innego słowa. Na przykład mata i tama to anagramy – mają dokładnie te same litery, tylko w innej kolejności. Sprawdzenie, czy dwa słowa są anagramami, to klasyczne zadanie na tekstach.
Jak to sprawdzić? Dwa słowa są anagramami, gdy mają te same litery w tej samej liczbie. Najprościej to policzyć: dla każdej litery patrzymy, ile razy występuje w pierwszym i w drugim słowie. Jeśli wszystkie liczby się zgadzają – to anagram.
Sprytny trik z jednym licznikiem: litery pierwszego słowa dodajemy, a litery drugiego odejmujemy – w tej samej tablicy. Jeśli na końcu każdy licznik wyszedł na zero, oba słowa mają identyczny zestaw liter, czyli są anagramami.
Krótszy sposób: posortować litery obu słów i porównać. Anagramy po posortowaniu dają identyczne ciągi (mata i tama po posortowaniu to oba aamt). Kod jest krótki, ale sortowanie jest trochę wolniejsze niż liczenie.
Na maturze: częste zadanie tekstowe. Zacznij od warunku koniecznego – słowa muszą mieć tę samą długość. Jeśli długości się różnią, od razu wiadomo, że anagramami nie są. Podobnie jak przy palindromie, zwykle trzeba też pominąć spacje i wielkość liter.
Prześledź metodę liczenia liter. Litery słowa 1 dodają do liczników, litery słowa 2 odejmują. Jeśli na końcu każdy licznik wyjdzie na zero, oba słowa mają ten sam zestaw liter – to anagram.
Naciśnij „Krok", aby policzyć kolejną literę, albo „Auto".
funkcja czy_anagram(A, B): jeżeli długość(A) ≠ długość(B): zwróć fałsz licznik ← tablica zer dla każdej litery dla każdej litery x z A: licznik[x] ← licznik[x] + 1 // dodajemy litery A dla każdej litery x z B: licznik[x] ← licznik[x] - 1 // odejmujemy litery B dla każdej litery x: jeżeli licznik[x] ≠ 0: zwróć fałsz zwróć prawda
def czy_anagram(a, b):
"""Sprawdza, czy słowa a i b mają te same litery (są anagramami)."""
if len(a) != len(b):
return False
licznik = {}
for x in a:
licznik[x] = licznik.get(x, 0) + 1 # dodajemy litery a
for x in b:
licznik[x] = licznik.get(x, 0) - 1 # odejmujemy litery b
for wartosc in licznik.values():
if wartosc != 0:
return False
return True
# Krótszy wariant: porównanie posortowanych liter
def czy_anagram_krotko(a, b):
return sorted(a) == sorted(b)
print(czy_anagram("mata", "tama")) # Wynik: True
print(czy_anagram("kot", "kok")) # Wynik: False#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
bool czy_anagram(string a, string b) {
if (a.size() != b.size()) return false;
sort(a.begin(), a.end()); // sortujemy litery obu slow
sort(b.begin(), b.end());
return a == b; // anagramy po posortowaniu sa identyczne
}
int main() {
cout << czy_anagram("mata", "tama") << "\n"; // Wynik: 1 (prawda)
cout << czy_anagram("kot", "kok") << "\n"; // Wynik: 0 (falsz)
}Palindrom to jedno słowo, które czyta się tak samo od tyłu (kajak). Anagram to dwa różne słowa złożone z tych samych liter (mata i tama). Palindrom sprawdzasz w jednym słowie, anagram – porównując dwa.
Bo jeśli słowa mają różną liczbę liter, nie mogą mieć tego samego zestawu liter – więc na pewno nie są anagramami. To kosztuje jedno porównanie i pozwala od razu skończyć, bez liczenia.
Liczenie daje czas O(n) – przechodzimy słowo raz. Sortowanie to O(n log n), czyli trochę wolniej, za to kod jest krótszy. Na maturze oba są w porządku; dla bardzo długich tekstów lepsze jest liczenie.
To zależy od zadania. Zwykle chcemy, żeby A i a liczyły się tak samo – wtedy przed sprawdzeniem zamieniamy wszystko na małe litery. Często pomijamy też spacje.
Dwa słowa są anagramami, gdy mają te same litery w tej samej liczbie. Wpisz odpowiedzi i kliknij Sprawdź.
W słowie mata litera a występuje razy, a litera m – raz. W słowie tama litera a też występuje razy. Zestawy liter są takie same, więc mata i tama anagramami.
Pierwsze, najtańsze sprawdzenie przed liczeniem liter: czy oba słowa mają tę samą .
Dla każdej pary napisz tak, jeśli to anagramy, albo nie:
| Para słów | Anagram? |
|---|---|
| kot – tok | |
| sok – kos | |
| kot – kok | |
| rama – mapa |
O(n)O(1)Czasowa O(n) dla metody z liczeniem – każde słowo przechodzimy tylko raz. Pamięć O(1), jeśli alfabet jest z góry ustalony (np. tablica liczników dla stałej liczby liter). Wariant z sortowaniem jest trochę wolniejszy: O(n log n).
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: