Правильная проверка палиндромов
Эффективно сравнивайте символы с обоих концов
«Правильная проверка палиндромов» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое палиндром
Палиндром читается одинаково слева направо и справа налево, например «топот» или «шалаш». Проверка на палиндром — классическая вводная задача. 🔁
Приём со срезом
Python умеет разворачивать строку с помощью среза s[::-1]. Сравните результат с исходной строкой — и получите проверку в одну строку.
s = 'level'
print(s == s[::-1]) # TrueСрез требует дополнительной памяти
Решение со срезом короткое, но создаёт полную перевёрнутую копию. Для огромных строк эта дополнительная память может иметь значение при жёстких ограничениях.
Способ с двумя указателями
Поставьте один указатель в начало, а другой — в конец. Сравнивайте символы и сдвигайте указатели навстречу друг другу. Это использует O(1) дополнительной памяти.
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
break
i += 1; j -= 1Остановка в середине
Указателям достаточно встретиться в середине. Когда i не меньше j, каждая пара уже совпала, и строка является палиндромом.
Несовпадение означает раннюю остановку
Цикл с двумя указателями может return False сразу после обнаружения различающейся пары. Обычно не приходится просматривать всю строку, что заметно ускоряет решение.
def is_pal(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]: return False
i += 1; j -= 1
return TrueОба метода работают за O(n)
В обоих случаях каждый символ просматривается не более одного раза, поэтому оба метода работают за линейное время. Различаются они только объёмом используемой дополнительной памяти.
Сначала нормализуйте строку
Во многих задачах регистр и пробелы не имеют значения. Сначала очистите строку: переведите её в нижний регистр и оставьте только буквы и цифры.
raw = 'A man, a plan'
clean = ''.join(c.lower() for c in raw if c.isalnum())Затем проверьте очищенную строку
После нормализации выполните обычную проверку на палиндром для очищенной версии. Это стандартный приём для палиндромов-предложений.
print(clean == clean[::-1])Указатели пропускают не-буквы
Вместо предварительной очистки два указателя могут пропускать все не буквенно-цифровые символы прямо в исходной строке. Так не приходится создавать вторую строку.
Палиндромы в подстроках
В более сложных задачах требуется искать палиндромные подстроки. Основная идея — расширение от центра: расширяйтесь в обе стороны от каждой позиции, пока крайние символы совпадают.
Быстрая проверка
Один вопрос о проверке палиндромов.
Повторение
Теперь Вы умеете проверять палиндромы быстрым срезом или экономными по памяти двумя указателями, а также нормализовать сложный ввод перед проверкой. 🎉
Часто задаваемые вопросы
Урок «Правильная проверка палиндромов» бесплатный?
Да — полный текст урока «Правильная проверка палиндромов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Правильная проверка палиндромов»?
Эффективно сравнивайте символы с обоих концов Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Правильная проверка палиндромов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Символы, ord и chr: полезные приёмы
- Подсчёт букв с таблицей частот
- Правильная проверка палиндромов
- Разделение, очистка и повторное объединение слов