Sprawdza czy słowo lub liczba czytane od lewej i od prawej dają ten sam ciąg znaków.
Palindrom to słowo, fraza lub liczba, które czytane od przodu i od tyłu dają ten sam wynik.
Przykłady: kajak, kobyłamamałybok, ABBA, 12321.
Algorytm: używamy dwóch wskaźników – jeden ustawiamy na początku, drugi na końcu tekstu. Porównujemy znaki: jeśli się różnią, to nie jest palindrom. Jeśli są identyczne, przesuwamy wskaźniki ku środkowi. Powtarzamy aż się spotkają.
Optymalizacja: wystarczy przejść połowę tablicy – stąd liniowa złożoność, ale ze stałą 1/2.
Pamięciowa O(1) – używamy tylko dwóch zmiennych pomocniczych, niezależnie od długości tekstu.
Wariant skrócony w Pythonie: s == s[::-1] – tworzy odwrócone słowo i porównuje. Krótki zapis, ale używa dodatkowej pamięci O(n). Na maturze lepiej napisać klasyczną wersję dwuwskaźnikową, bo w niektórych zadaniach takie wbudowane operacje mogą być zabronione.
funkcja czy_palindrom(s, n): lewy ← 0 prawy ← n - 1 // przesuwamy wskaźniki ku środkowi dopóki lewy < prawy: jeżeli s[lewy] ≠ s[prawy]: zwróć fałsz lewy ← lewy + 1 prawy ← prawy - 1 zwróć prawda
def czy_palindrom(s):
lewy = 0
prawy = len(s) - 1
while lewy < prawy:
if s[lewy] != s[prawy]:
return False
lewy += 1
prawy -= 1
return True
# Przykład użycia
print(czy_palindrom("kajak"))
# Wynik: True
print(czy_palindrom("python"))
# Wynik: False
print(czy_palindrom("12321"))
# Wynik: TrueO(n)O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: