Valid Palindrome

Q: Jaka jest złożoność czasowa problemu Valid Palindrome?

Oba podejścia działają w czasie O(n) , ponieważ każdy znak jest sprawdzany stałą liczbę razy. Wstępne oczyszczenie wymaga dodatkowej pamięci O(n) na kopię. Wersja z dwoma wskaźnikami wymaga dodatkowej pamięci O(1) , ponieważ przechowuje tylko dwa indeksy.

Q: Jak sprawdzić, czy ciąg jest palindromem, ignorując znaki niealfanumeryczne?

Umieść po jednym wskaźniku na każdym końcu ciągu znaków. Przesuwaj wskaźnik dalej, mijając każdy znak, który nie jest literą ani cyfrą, a gdy oba wskaźniki znajdą się na literach lub cyfrach, porównaj je po zamianie na małe litery. Jeśli każda porównana para znaków jest zgodna, aż wskaźniki się spotkają, ciąg znaków jest palindromem.

Q: Czy pusty ciąg znaków jest palindromem?

Tak. Pusty tekst czyta się tak samo w obu kierunkach, więc ciąg taki jak ?!-_ , którego wszystkie znaki są pomijane, zwraca true . Oba podejścia osiągają to bez dodatkowego kodu: oczyszczony tekst jest równy swojemu pustemu odwróceniu, a dwa wskaźniki nigdy nie znajdują pary, która się różni.

Q: Dlaczego warto używać dwóch wskaźników zamiast odwracać ciąg znaków?

Odwracanie wymaga oczyszczonej kopii i odwróconej kopii, co oznacza dodatkowe zużycie pamięci rzędu O(n) . Dwa wskaźniki porównują te same pary w miejscu i mogą zatrzymać się przy pierwszej niezgodności, często już po kilku krokach. W ramach pytania uzupełniającego osoby prowadzące rozmowy kwalifikacyjne zwykle proszą o tę wersję.

ŁatweDwa wskaźniki

+10

Otrzymujesz ciąg znaków s. Zachowaj tylko litery i cyfry, traktuj wielkie i małe litery jako takie same, a następnie zdecyduj, czy to, co pozostało, czytane od lewej do prawej jest takie samo jak czytane od prawej do lewej. Zwróć true, jeśli tak jest, a w przeciwnym razie false.

Wszystkie pozostałe znaki, takie jak ., !, ?, :, ;, - lub _, są ignorowane. Jeśli s nie zawiera żadnych liter ani cyfr, nic nie pozostaje, a pusty tekst jest uznawany za palindrom.

Funkcja

isPalindrome(s: string) → boolean

sstring: tekst do sprawdzenia, wraz z interpunkcją
Zwracaboolean: prawda, jeśli litery i cyfry w s czytane w obu kierunkach są takie same, bez uwzględniania wielkości liter

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera angielskie litery, cyfry i znaki interpunkcyjne . ! ? : ; - _, bez spacji.

Przykłady

Wejście: s = "Was_it_a_car_or_a_cat_I_saw?"
Wyjście: true
Wyjaśnienie: Usuń podkreślenia i znak zapytania, a wielkie litery zamień na małe: otrzymasz wasitacaroracatisaw, które czytane od tyłu jest takie samo.

Wejście: s = "race-a-car"
Wyjście: false
Wyjaśnienie: Bez łączników tekst to raceacar. Czytany od prawej zaczyna się od raca zamiast race: środkowe e ma a jako swój lustrzany odpowiednik, więc odpowiedź to false.

Wejście: s = "Step-on-no-pets!"
Wyjście: true
Wyjaśnienie: Zachowany tekst to steponnopets. Wielka litera S pasuje do końcowej litery s, ponieważ wielkość liter jest ignorowana, a łączniki i znak ! nie mają znaczenia.

+25 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz rozstrzygnąć to przy użyciu dodatkowej pamięci O(1), bez tworzenia oczyszczonej kopii s?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Samo sprawdzanie palindromu jest dobrze znane: pierwszy pozostawiony znak musi być równy ostatniemu, drugi — przedostatniemu i tak dalej. Trudność w tej wersji polega na tym, że porównywane znaki nie znajdują się na symetrycznych indeksach s, ponieważ znaki interpunkcyjne są nierównomiernie rozmieszczone po obu stronach. Możesz najpierw je usunąć albo pozwolić dwóm wskaźnikom pomijać je, gdy przesuwają się ku sobie.

Oczyść ciąg znaków, a następnie porównaj go z jego odwróceniem

Intuicja

Zbuduj tekst, którego dotyczy pytanie w zadaniu. Przejdź po s, zachowaj każdą literę lub cyfrę małą literą i pomiń wszystko inne. Dla Step-on-no-pets! otrzymujemy steponnopets. Teraz chodzi o zwykłe pytanie o palindrom: czy ten tekst jest równy swojemu odwróceniu?

To rozwiązanie jest poprawne, ponieważ czyszczenie usuwa dokładnie te znaki, które zgodnie z treścią zadania należy ignorować, i zmienia wielkość liter, którą również należy ignorować. Jeśli s nie zawiera żadnych liter ani cyfr, oczyszczony tekst jest pusty, a pusty tekst jest równy swojemu odwróceniu, więc odpowiedzią jest true — bez żadnych szczególnych przypadków.

Każdy znak jest odczytywany raz podczas czyszczenia i jeszcze raz podczas porównywania, więc czas działania wynosi O(n). Oczyszczona kopia i jej odwrócenie zajmują dodatkowe O(n) pamięci — to właśnie ten koszt eliminuje następne podejście.

Algorytm

Utwórz pusty tekst cleaned.
Dla każdego znaku w s, jeśli jest literą lub cyfrą, dodaj go w postaci małej litery.
Odwróć cleaned.
Zwróć informację, czy cleaned jest równe swojej odwróconej wersji.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Dwa wskaźniki pomijające znaki interpunkcyjne

Intuicja

Oczyszczona kopia służy tylko do porównywania symetrycznych znaków. To samo porównanie możesz wykonać bezpośrednio na s. Umieść left na pierwszym indeksie, a right na ostatnim. Na każdym kroku, jeśli left wskazuje znak interpunkcyjny, przesuń go w prawo; jeśli right wskazuje znak interpunkcyjny, przesuń go w lewo. Gdy oba wskaźniki wskazują litery lub cyfry, porównaj te znaki zapisane małymi literami. Niezgodność oznacza false; zgodność oznacza, że oba wskaźniki przesuwają się do środka.

Dlaczego to jest to samo sprawdzenie? Wskaźniki zawsze zatrzymują się na kolejnym zachowanym znaku z każdego końca, więc odwiedzają pary (pierwszy zachowany, ostatni zachowany), (drugi zachowany, przedostatni zachowany) i tak dalej — dokładnie te same pary, które sprawdza porównanie z odwróconym ciągiem. W Abc-dcbX pierwszą parę stanowią A i X, a wynik to false po jednym porównaniu.

Na każdym kroku przesuwa się co najmniej jeden wskaźnik, a zatrzymują się one, gdy się spotkają, więc pętla wykonuje się co najwyżej n razy. Poza dwoma indeksami nic nie jest przechowywane, co oznacza dodatkowe zużycie pamięci równe O(1).

Algorytm

Ustaw left = 0 i right = n-1.
Gdy left < right: jeśli s[left] nie jest literą ani cyfrą, zwiększ left i kontynuuj.
W przeciwnym razie, jeśli s[right] nie jest literą ani cyfrą, zmniejsz right i kontynuuj.
W przeciwnym razie porównaj oba znaki zapisane małymi literami. Jeśli się różnią, zwróć false; jeśli są takie same, przesuń oba wskaźniki do środka.
Gdy wskaźniki się spotkają, zwróć true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Pułapki i przypadki brzegowe

Większość błędów wynika z pomijanych znaków i wielkości liter.

Porównywanie s[i] z s[n-1-i] w surowym ciągu znaków. a-ba jest palindromem po usunięciu łącznika, ale surowym odbiciem - na indeksie 1 jest b na indeksie 2.
Przesuwanie obu wskaźników, gdy tylko jeden z nich wskazuje znak interpunkcyjny. Pomijaj znaki po jednej stronie naraz, bo inaczej obie strony przestaną być zsynchronizowane.
Pomijanie znaków interpunkcyjnych w wewnętrznej pętli, która wykracza poza drugi wskaźnik. W przypadku ?!-_ nieograniczona pętla wewnętrzna wychodzi poza koniec ciągu znaków; sprawdzaj left < right przy każdym przesunięciu.
Traktowanie cyfr jak nieistotnych znaków. 0P to false: cyfra 0 zostaje i jest porównywana, a ponadto nie jest literą p.
Zwracanie false, gdy nic nie zostaje. Ciąg zawierający wyłącznie znaki interpunkcyjne, taki jak ., ma pusty oczyszczony tekst, który jest palindromem.
Ciąg złożony wyłącznie z cyfr, taki jak 12321, może zostać przekazany do PHP i R jako liczba. Najpierw przekonwertuj go na ciąg znaków.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu Valid Palindrome?

Oba podejścia działają w czasie O(n), ponieważ każdy znak jest sprawdzany stałą liczbę razy. Wstępne oczyszczenie wymaga dodatkowej pamięci O(n) na kopię. Wersja z dwoma wskaźnikami wymaga dodatkowej pamięci O(1), ponieważ przechowuje tylko dwa indeksy.

Jak sprawdzić, czy ciąg jest palindromem, ignorując znaki niealfanumeryczne?

Umieść po jednym wskaźniku na każdym końcu ciągu znaków. Przesuwaj wskaźnik dalej, mijając każdy znak, który nie jest literą ani cyfrą, a gdy oba wskaźniki znajdą się na literach lub cyfrach, porównaj je po zamianie na małe litery. Jeśli każda porównana para znaków jest zgodna, aż wskaźniki się spotkają, ciąg znaków jest palindromem.

Czy pusty ciąg znaków jest palindromem?

Tak. Pusty tekst czyta się tak samo w obu kierunkach, więc ciąg taki jak ?!-_, którego wszystkie znaki są pomijane, zwraca true. Oba podejścia osiągają to bez dodatkowego kodu: oczyszczony tekst jest równy swojemu pustemu odwróceniu, a dwa wskaźniki nigdy nie znajdują pary, która się różni.

Dlaczego warto używać dwóch wskaźników zamiast odwracać ciąg znaków?

Odwracanie wymaga oczyszczonej kopii i odwróconej kopii, co oznacza dodatkowe zużycie pamięci rzędu O(n). Dwa wskaźniki porównują te same pary w miejscu i mogą zatrzymać się przy pierwszej niezgodności, często już po kilku krokach. W ramach pytania uzupełniającego osoby prowadzące rozmowy kwalifikacyjne zwykle proszą o tę wersję.

Python

def isPalindrome(s):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "Was_it_a_car_or_a_cat_I_saw?"

Oczekiwane

true