Palindrome String

Odczytywanie s tak samo w obu kierunkach oznacza, że s jest równe swojemu odwróceniu. Odwróć je więc i porównaj: racecar po odwróceniu to racecar, a coddy po odwróceniu to yddoc, co jest inne.

Tworzenie odwróconego ciągu i porównywanie ich sprawia, że każdy znak jest odwiedzany raz, więc złożoność czasowa wynosi O(n). Odwrócona kopia zawiera dodatkowe n znaków, co oznacza O(n) dodatkowej pamięci: przy n = 5 × 10^4 to 50 000 znaków utworzonych tylko po to, by je porównać i odrzucić.

Ta metoda wykonuje też całą pracę za każdym razem. O tym, że coddy nie jest palindromem, decydują jego pierwsza i ostatnia litera, a mimo to ta metoda odwraca wszystkie pięć liter, zanim je porówna.

Odwrócenie przenosi znak z indeksu 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ę na tej liście dwa razy, więc sprawdzaj tylko lewą połowę. Ustaw left na indeksie 0, a right na indeksie n-1, porównaj oba znaki i przesuń oba wskaźniki o jeden krok do środka.

Zatrzymaj się, gdy wskaźniki się spotkają lub miną. W racecar sprawdzają pary indeksów (0, 6), (1, 5) i (2, 4), a następnie spotykają się na indeksie 3, gdzie znajduje się środkowe e, które nie potrzebuje pary. W abba sprawdzają (0, 3) i (1, 2), a potem mijają się. Pierwsza różniąca się para dowodzi, że odpowiedź to false, więc od razu zwracasz wynik: dla coddy rozstrzygnięcie następuje po jednym porównaniu.

Wykonuje się najwyżej n / 2 porównań, co oznacza czas O(n), a jedyną używaną pamięcią są dwa indeksy, czyli O(1) miejsca. Wyjątkiem jest R: najpierw odczytuje ciąg jako wektor kodów znaków, co kosztuje O(n).