Обнаружение палиндрома

Палиндром — это слово, фраза, число или другая последовательность символов, которая одинаково читается в обоих направлениях (слева направо и справа налево). Примеры:

• Слова: "топот", "казак", "дед"

• Фразы: "А роза упала на лапу Азора"

• Числовые: 12321, 555555

В программировании задача определения палиндромов встречается часто и имеет несколько эффективных решений.

Основные алгоритмы проверки на палиндром

 Метод двух указателей

Самый эффективный алгоритм с точки зрения памяти (O(1)):

1. Инициализировать два указателя: один в начале строки, другой в конце

2. Сравнивать символы на позициях указателей

3. Если символы не совпадают — это не палиндром

4. Сдвигать указатели к центру, пока они не встретятся

def is_palindrome1(s):
    s = s.replace(' ', '').lower()
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Сложность: O(n) по времени, O(1) по памяти

Метод реверса строки

Простой и понятный, но менее эффективный по памяти:

1. Развернуть строку

2. Сравнить с оригиналом

def is_palindrome1(s):
    s = s.lower().replace(' ', '')
    return s == s[::-1]

Сложность: O(n) по времени и памяти (из-за создания новой строки)