Что такое палиндром и как проверить его на Python

Что такое палиндром? Напишите проверку

Палиндром — строка или последовательность, которая читается одинаково слева направо и справа налево. Проверку можно сделать сравнением строки с её перевёрнутой копией либо алгоритмом двух указателей; оба варианта работают за O(n).

Подробный ответ

Что такое палиндром

Палиндром — это последовательность символов, которая одинаково читается в прямом и обратном направлении. Например, level, radar и топот — палиндромы.

Простое решение

def is_palindrome(value: str) -> bool:
    return value == value[::-1]

Проверка без учёта регистра и пробелов

Часто условие задачи требует игнорировать регистр, пробелы и знаки препинания. Тогда строку сначала нормализуют.

def is_palindrome(value: str) -> bool:
    normalized = ''.join(
        character.lower()
        for character in value
        if character.isalnum()
    )

    return normalized == normalized[::-1]

print(is_palindrome('А роза упала на лапу Азора'))
# True

Решение двумя указателями

def is_palindrome(value: str) -> bool:
    left = 0
    right = len(value) - 1

    while left < right:
        if value[left] != value[right]:
            return False

        left += 1
        right -= 1

    return True

Сложность

Временная сложность равна O(n), потому что нужно сравнить символы строки. Решение со срезом создаёт новую строку и требует O(n) дополнительной памяти. Вариант с двумя указателями использует O(1) дополнительной памяти, если не учитывать входную строку.

Как ответить на собеседовании

Палиндром одинаково читается слева направо и справа налево. В простом случае проверяю value == value[::-1]. Если нужно игнорировать пробелы и регистр, сначала нормализую строку. Алгоритм работает за O(n); вариант с двумя указателями использует O(1) дополнительной памяти.