Algorytmy i struktury danych · Junior · Pytanie 43 z 75
Jak sprawdzić, czy napis jest palindromem, w czasie O(n) i z O(1) dodatkowej pamięci?
- 1Posortować znaki i porównać z oryginałem
- ✓Poprawna odpowiedź: Porównywać znaki z obu końców, idąc ku środkowi
- 3Porównać napis z
str.split("").reverse().join("")
Wyjaśnienie
Dwa wskaźniki porównują s[i] z s[j] i zatrzymują się na pierwszej różnicy. Odwrócenie też działa, ale tworzy nowy napis, więc zajmuje O(n) pamięci. Sortowanie jest błędne: gubi kolejność znaków.