Алгоритми та структури даних · Junior · Запитання 43 з 75
Як перевірити, чи рядок є паліндромом, за O(n) часу й O(1) додаткової пам'яті?
- 1Відсортувати символи й порівняти з оригіналом
- ✓Правильна відповідь: Порівнювати символи з обох кінців, рухаючись до середини
- 3Порівняти рядок із
str.split("").reverse().join("")
Пояснення
Два вказівники порівнюють s[i] із s[j] і зупиняються на першій розбіжності. Розворот теж працює, але створює новий рядок, тобто займає O(n) пам'яті. Сортування не підходить: воно втрачає порядок символів.