Palindrom - różne podejścia

1. Czym jest palindrom?

Palindrom to słowo, zdanie lub ciąg znaków, który brzmi tak samo czytany od przodu i od tyłu.

Przykłady:

✅ Słowa:
- kajak
- radar
- poziom
- potop
- noon
- racecar

✅ Zdania (ignorując spacje i znaki):
- "A man a plan a canal Panama"
- "Kobyła ma mały bok"
- "Was it a car or a cat I saw?"

✅ Liczby:
- 121
- 12321
- 1221

2. Najprostsze podejście – odwracanie stringa

2.1. Metoda 1: Slicing

Złożoność: - Czasowa: O(n) - Pamięciowa: O(n) – tworzy nowy string

3. Podejście z dwoma wskaźnikami

3.1. Bez dodatkowej pamięci:

Zalety: - O(1) pamięci ✅ - Przerywa wcześnie (gdy znajdzie różnicę)

3.2. Wizualizacja:

"kajak"
 ↑   ↑   left=0, right=4, k==k ✓
  ↑ ↑    left=1, right=3, a==a ✓
   ↑     left=2, right=2, STOP (left >= right)

Wynik: True

"python"
 ↑    ↑  left=0, right=5, p!=n ✗

Wynik: False (przerwane wcześnie!)

4. Podejście rekurencyjne

Złożoność: - Czasowa: O(n) - Pamięciowa: O(n) – stos rekurencji + nowe stringi

Uwaga: Mniej efektywne niż podejście iteracyjne.

5. Palindrom ignorując wielkość liter

6. Palindrom ignorując spacje i znaki specjalne

6.1. Czyszczenie tekstu:

6.2. Z dwoma wskaźnikami:

Zaleta: O(1) dodatkowej pamięci! ✅

7. Sprawdzanie podstringów palindromicznych

7.1. Czy dany substring jest palindromem?

7.2. Najdłuższy palindromiczny substring:

Złożoność: O(n²) czas, O(1) pamięć

8. Liczenie palindromicznych substringów

Złożoność: O(n²)

9. Palindrom liczby

9.1. Bez konwersji na string:

Złożoność: O(log n) – liczba cyfr

10. Minimalna liczba usunięć do palindromu

Złożoność: O(n²)

11. Permutacja palindromu

11.1. Sprawdzenie, czy permutacja może być palindromem:

11.2. Generowanie palindromu z permutacji:

12. Partycjonowanie na palindromy

Złożoność: O(n × 2^n)

13. Benchmark różnych metod

14. Podsumowanie

Palindrom:

  • String czytany tak samo od przodu i od tyłu
  • Przykłady: "kajak", "radar", "A man a plan a canal Panama"

Metody wykrywania:

Metoda Czas Pamięć Zalety
Slicing s[::-1] O(n) O(n) Najprostsza
Dwa wskaźniki O(n) O(1) ✅ Oszczędność pamięci
Rekurencja O(n) O(n) Elegancka (ale wolniejsza)

Implementacje podstawowe:

Problemy zaawansowane:

  • Najdłuższy palindrom: O(n²) z rozszerzaniem wokół centrum
  • Liczenie palindromów: O(n²)
  • Minimalne usunięcia: O(n²) z LCS
  • Permutacja palindromu: O(n) z liczeniem znaków
  • Partycjonowanie: O(n × 2^n) z backtrackingiem

Kluczowe obserwacje:

Palindrom nieparzystej długości:
  "racecar" → centrum = 'e'
   ←←←e→→→

Palindrom parzystej długości:
  "abba" → centrum = między 'b' i 'b'
   ←←||→→

Warunek permutacji palindromu:

Permutacja może być palindromem gdy:
- Długość parzysta: wszystkie znaki występują parzystą liczbę razy
- Długość nieparzysta: dokładnie 1 znak występuje nieparzystą liczbę razy

Przykład: "aab" → can be palindrome (a:2, b:1)

Zastosowania:

  • Walidacja danych (numery rejestracyjne, kody)
  • Bioinformatyka (sekwencje DNA)
  • Kompresja tekstu
  • Problemy algorytmiczne (LeetCode, interviews)

Co dalej warto poznać:

  • Manacher's Algorithm – najdłuższy palindrom w O(n) ✅
  • Palindromiczne drzewa – zaawansowana struktura
  • Palindromy w grafach – ścieżki palindromiczne
  • Dynamic Programming – problemy optymalizacyjne z palindromami
  • Anagramy – pokrewny problem tekstowy
Wróć do spisu lekcji