Palindrome String

Q: Jak sprawdzić, czy ciąg znaków jest palindromem?

Porównuj pierwszy znak z ostatnim, drugi z przedostatnim i tak dalej, kierując się ku środkowi. Jeśli którakolwiek para się różni, ciąg znaków nie jest palindromem. Dwa indeksy, które zaczynają na obu końcach i przesuwają się do środka, wykonują to w jednym przebiegu.

Q: Czy potrafisz sprawdzić, czy coś jest palindromem, bez użycia dodatkowej pamięci?

Tak. Sprawdzanie dwoma wskaźnikami odczytuje znaki w miejscu i przechowuje dwa indeksy, więc zużywa O(1) dodatkowej pamięci. Porównanie s z jego odwróceniem jest krótsze do zapisania, ale tworzy drugi ciąg znaków o długości n .

Q: Jaka jest złożoność czasowa sprawdzania, czy ciąg znaków jest palindromem?

O(n) dla ciągu znaków o długości n . Sprawdzenie za pomocą dwóch wskaźników wykonuje maksymalnie n / 2 porównań i kończy się przy pierwszej niezgodności, więc coddy wymaga jednego porównania.

Q: Czy pojedynczy znak jest palindromem?

Tak, odczytuje się tak samo w obu kierunkach. W pętli z dwoma wskaźnikami left i right oba zaczynają od indeksu 0, pętla nigdy się nie wykonuje, a funkcja zwraca true .

PoczątkującyDwa wskaźniki Tablice i napisy

+10

Ciąg znaków jest palindromem, gdy czytany od lewej do prawej jest taki sam jak czytany od prawej do lewej, tak jak level. Napisz funkcję, która otrzymuje ciąg znaków s składający się z małych liter alfabetu angielskiego i zwraca true, jeśli s jest palindromem, a w przeciwnym razie false.

Funkcja

isPalindrome(s: string) → boolean

sstring: mały ciąg znaków do sprawdzenia
Zwracaboolean: true, gdy s czyta się tak samo w obu kierunkach

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera wyłącznie małe litery alfabetu angielskiego (a–z).

Przykłady

Wejście: s = "racecar"
Wyjście: true
Wyjaśnienie: Porównuj od zewnątrz do środka: r z r, a z a, c z c. Środkowe e nie ma pary i jej nie potrzebuje, więc odpowiedź to true.

Wejście: s = "abba"
Wyjście: true
Wyjaśnienie: Przy parzystej długości każda litera ma swoją parę: dwa a pasują do siebie, a dwa b pasują do siebie, więc odpowiedzią jest true.

Wejście: s = "coddy"
Wyjście: false
Wyjaśnienie: Pierwsza litera c i ostatnia litera y już się różnią, więc coddy nie jest palindromem, a odpowiedź to false.

Pytanie dodatkowe

Jak zmienić dwa wskaźniki, aby pomijały spacje i znaki interpunkcyjne oraz ignorowały wielkość liter, tak aby Was it a car or a cat I saw było uznawane za palindrom?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Palindrom jest równy swojemu odwróceniu, więc możesz utworzyć odwróconą wersję i porównać je. Nie potrzebujesz kopii: pierwszy znak musi pasować do ostatniego, drugi do przedostatniego i tak dalej. Dwa indeksy przesuwające się do środka sprawdzają te pary na miejscu i zatrzymują się przy pierwszej niezgodności.

Porównaj ciąg znaków z jego odwróceniem

Intuicja

Odwróć s i porównaj: po odwróceniu racecar otrzymujemy racecar, a po odwróceniu coddy otrzymujemy yddoc. Ciąg znaków czyta się tak samo w obu kierunkach dokładnie wtedy, gdy jest równy swojemu odwróceniu.

Złożoność czasowa wynosi O(n), ale odwrócona kopia wymaga dodatkowego miejsca O(n), czyli 50,000 znaków dla n = 5 × 10^4. Praca jest też zawsze wykonywana w całości: o coddy można zdecydować na podstawie pierwszej i ostatniej litery, a mimo to najpierw odwracane jest wszystkich pięć znaków.

Algorytm

Utwórz odwróconą wersję s za pomocą funkcji odwracającej dostępnej w języku lub pętli przechodzącej od ostatniego znaku do pierwszego.
Porównaj odwróconą wersję z s.
Zwróć true, jeśli są równe, a w przeciwnym razie false.

def isPalindrome(s):
    return s == s[::-1]

Dwa wskaźniki z obu końców

Intuicja

Odwrócenie przenosi indeks i na indeks n-1-i, więc s jest równe swojemu odwróceniu dokładnie wtedy, gdy s[i] jest równe s[n-1-i] dla każdego i. Każda para pojawia się w tym warunku dwukrotnie, więc wystarczy sprawdzić lewą połowę. W racecar parami są (0, 6), (1, 5) i (2, 4); środkowe e na indeksie 3 nie potrzebuje pary.

Pierwsza różniąca się para dowodzi, że odpowiedź to false, więc wynik dla coddy można ustalić po jednym porównaniu. Wykonuje się najwyżej n / 2 porównań, co oznacza czas O(n), a dwa indeksy wymagają O(1) pamięci. R najpierw odczytuje ciąg jako wektor kodów znaków, co kosztuje O(n).

Algorytm

Ustaw left = 0 i right = n-1.
Dopóki left < right, porównuj s[left] z s[right].
Jeśli się różnią, zwróć false.
W przeciwnym razie dodaj 1 do left, odejmij 1 od right i powtórz.
Gdy wskaźniki się spotkają lub miną, każda para jest dopasowana: zwróć true.

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

Pułapki i przypadki brzegowe

Zwracanie true, gdy tylko jedna para pasuje. abca przechodzi test pary zewnętrznej i nie przechodzi testu pary wewnętrznej, więc true pojawia się dopiero po pętli.
Ustawienie right na n zamiast na n-1, co powoduje odczyt poza końcem (w C jest to terminujące '\0'). W Lua i R indeksy biegną od 1 do n, więc tam right zaczyna się od n.
Porównywanie ciągów znaków za pomocą == w C. reversed == s porównuje dwa wskaźniki i zwraca false dla kopii; użyj strcmp.
Tworzenie odwróconego ciągu za pomocą result = result + ch. Każdy krok kopiuje dotychczasowy ciąg: około 1.25 × 10^9 kopii znaków dla 50,000 liter.
Indeksowanie ciągu znaków w Swift za pomocą liczby całkowitej: kod się nie skompiluje. Przejdź po s.utf8 albo skopiuj znaki do tablicy.

Najczęstsze pytania4

Jak sprawdzić, czy ciąg znaków jest palindromem?

Porównuj pierwszy znak z ostatnim, drugi z przedostatnim i tak dalej, kierując się ku środkowi. Jeśli którakolwiek para się różni, ciąg znaków nie jest palindromem. Dwa indeksy, które zaczynają na obu końcach i przesuwają się do środka, wykonują to w jednym przebiegu.

Czy potrafisz sprawdzić, czy coś jest palindromem, bez użycia dodatkowej pamięci?

Tak. Sprawdzanie dwoma wskaźnikami odczytuje znaki w miejscu i przechowuje dwa indeksy, więc zużywa O(1) dodatkowej pamięci. Porównanie s z jego odwróceniem jest krótsze do zapisania, ale tworzy drugi ciąg znaków o długości n.

Jaka jest złożoność czasowa sprawdzania, czy ciąg znaków jest palindromem?

O(n) dla ciągu znaków o długości n. Sprawdzenie za pomocą dwóch wskaźników wykonuje maksymalnie n / 2 porównań i kończy się przy pierwszej niezgodności, więc coddy wymaga jednego porównania.

Czy pojedynczy znak jest palindromem?

Tak, odczytuje się tak samo w obu kierunkach. W pętli z dwoma wskaźnikami left i right oba zaczynają od indeksu 0, pętla nigdy się nie wykonuje, a funkcja zwraca true.

def isPalindrome(s):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

s = "racecar"

Oczekiwany wynik

true