Poprawne sprawdzanie palindromów
Wydajne porównywanie od obu końców
Poprawne sprawdzanie palindromów to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Czym jest palindrom
Palindrom brzmi tak samo czytany od przodu i od tyłu, jak racecar lub level. Sprawdzanie, czy coś jest palindromem, to klasyczne zadanie na rozgrzewkę. 🔁
Sztuczka z wycinkiem
Python potrafi odwrócić napis za pomocą wycinka s[::-1]. Porównaj go z oryginałem, aby uzyskać sprawdzenie w jednym wierszu.
s = 'level'
print(s == s[::-1]) # TrueWycinek wymaga dodatkowej pamięci
Podejście z wycinkiem jest krótkie, ale tworzy całą odwróconą kopię. W przypadku bardzo długich napisów ta dodatkowa pamięć może mieć znaczenie przy ścisłych limitach.
Sposób z dwoma wskaźnikami
Umieść jeden wskaźnik na początku, a drugi na końcu. Porównuj znaki i przesuwaj wskaźniki do środka. To rozwiązanie wymaga O(1) dodatkowej pamięci.
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
break
i += 1; j -= 1Zatrzymaj się w połowie
Wskaźniki muszą jedynie spotkać się w połowie. Gdy i nie jest mniejsze od j, każda para została już dopasowana i napis jest palindromem.
Niezgodność oznacza wcześniejsze zakończenie
Pętla z dwoma wskaźnikami może zwrócić False natychmiast po wykryciu różnicy w parze. Rzadko trzeba wtedy przeglądać cały napis, co zapewnia przyspieszenie.
def is_pal(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]: return False
i += 1; j -= 1
return TrueOba rozwiązania mają O(n)
W obu przypadkach każdy znak jest sprawdzany najwyżej raz, więc obie metody działają w czasie liniowym. Różnią się tylko ilością używanej dodatkowej pamięci.
Najpierw znormalizuj napis
W wielu zadaniach wielkość liter i spacje są ignorowane. Najpierw należy oczyścić napis, zamieniając litery na małe i pozostawiając tylko litery oraz cyfry.
raw = 'A man, a plan'
clean = ''.join(c.lower() for c in raw if c.isalnum())Następnie sprawdź oczyszczony napis
Po normalizacji wykonaj standardowe sprawdzenie palindromu na wersji oczyszczonej. To typowy schemat dla palindromów będących zdaniami.
print(clean == clean[::-1])Wskaźniki pomijają znaki inne niż litery
Zamiast najpierw oczyszczać napis, można użyć dwóch wskaźników, które bezpośrednio pomijają znaki niealfanumeryczne. Dzięki temu nie trzeba w ogóle tworzyć drugiego napisu.
Palindromiczne podnapisy
Trudniejsze zadania dotyczą palindromicznych podnapisów. Podstawowa metoda to rozszerzanie od środka: należy rozszerzać zakres od każdej pozycji, dopóki końce są zgodne.
Szybkie sprawdzenie
Jedno pytanie dotyczące sprawdzania palindromów.
Podsumowanie
Można teraz sprawdzać palindromy za pomocą szybkiego wycinka albo oszczędnego pamięciowo rozwiązania z dwoma wskaźnikami, a także normalizować nieuporządkowane dane wejściowe przed sprawdzeniem. 🎉
Często zadawane pytania
Czy lekcja „Poprawne sprawdzanie palindromów” jest bezpłatna?
Tak — pełny tekst „Poprawne sprawdzanie palindromów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Poprawne sprawdzanie palindromów”?
Wydajne porównywanie od obu końców Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Poprawne sprawdzanie palindromów”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sztuczki z znakami, ord i chr
- Zliczanie liter za pomocą tabeli częstości
- Poprawne sprawdzanie palindromów
- Dzielenie, stripowanie i ponowne łączenie słów