Как проверить, является ли строка палиндромом?

Палиндром — строка, которая читается одинаково слева направо и справа налево. Самый простой способ — развернуть строку и сравнить: s == s[::-1] в Python. На собеседовании от junior-разработчика обычно ждут два подхода: через реверс и через два указателя. Важно обсудить, как учитывать регистр, пробелы и знаки препинания — это часто является частью задачи.

• Подход 1: разворот строки. В Python s[::-1] создаёт новую строку за O(n) памяти. Встроенный reverse в C#/Java даёт такую же сложность. Минус: для длинных строк тратится лишняя память.
• Подход 2: два указателя. Ставим left = 0, right = len(s)-1. Сравниваем символы, двигаем указатели навстречу, пока left < right. Преимущество: O(1) дополнительной памяти, O(n) времени. Если нужен case-insensitive — приводим символы к одному регистру перед сравнением.
• Фильтрация лишних символов. Если условие «только буквы и цифры» (как в LeetCode 125), то при движении указателей пропускаем неалфавитно-цифровые символы. Для этого можно использовать char.IsLetterOrDigit(c) в C# или c.isalnum() в Python.
• Граничные случаи. Пустая строка и строка из одного символа — палиндромы. null лучше обрабатывать отдельно — выбросить исключение или вернуть false в зависимости от контекста.
• Сложность. Идеальное решение — O(n) времени и O(1) памяти. Реверс даёт O(n) по памяти, что тоже принимается, но вопрос про оптимизацию всплывёт.

Пример реализации на Python (два указателя, без фильтрации):

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Для варианта с фильтрацией добавляем пропуск:

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True