Как реализуешь проверку на полиндром в Python?

Как реализуешь проверку на палиндром в Python?

Проверка палиндрома — классическая задача, которая выглядит простой, но имеет множество вариантов реализации с разными компромиссами по производительности и читаемости.

1. Базовый подход: сравнение со своей инверсией

Самый простой и понятный способ:

def is_palindrome_simple(s: str) -> bool:
    # Удаляем пробелы, приводим к нижнему регистру
    cleaned = s.replace(' ', '').lower()
    # Сравниваем с перевёрнутой строкой
    return cleaned == cleaned[::-1]

# Тесты
print(is_palindrome_simple('A man a plan a canal Panama'))  # True
print(is_palindrome_simple('hello'))  # False
print(is_palindrome_simple('racecar'))  # True

Плюсы: простота, одна строка логики Минусы: создаёт новую строку в памяти, не учитывает пунктуацию

2. Более строгая проверка с пунктуацией

Если нужно игнорировать пунктуацию и специальные символы:

import string

def is_palindrome_strict(s: str) -> bool:
    # Оставляем только буквы и цифры
    cleaned = ''.join(
        char.lower() 
        for char in s 
        if char.isalnum()
    )
    return cleaned == cleaned[::-1]

# Тесты
print(is_palindrome_strict('A man, a plan, a canal: Panama'))  # True
print(is_palindrome_strict('race a car'))  # False
print(is_palindrome_strict('0P'))  # False
print(is_palindrome_strict('a.'))  # True

3. Двухуказательный подход (О(n/2) операции)

Эффективнее в плане памяти — не создаём новую строку:

def is_palindrome_two_pointers(s: str) -> bool:
    cleaned = ''.join(
        char.lower() 
        for char in s 
        if char.isalnum()
    )
    
    left = 0
    right = len(cleaned) - 1
    
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    
    return True

# Тесты
print(is_palindrome_two_pointers('A man, a plan, a canal: Panama'))  # True

Плюсы: не создаёт перевёрнутую строку, может ранний выход Минусы: всё ещё создаёт cleaned версию

4. Без создания новой строки (максимум эффективности)

def is_palindrome_optimized(s: str) -> bool:
    left = 0
    right = 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

# Тесты
print(is_palindrome_optimized('A man, a plan, a canal: Panama'))  # True
print(is_palindrome_optimized('.,'))  # True

Плюсы: O(1) дополнительной памяти, максимально эффективно Минусы: больше кода, сложнее читать

5. С использованием deque (для углубленного собеседования)

from collections import deque

def is_palindrome_deque(s: str) -> bool:
    cleaned = deque(
        char.lower() 
        for char in s 
        if char.isalnum()
    )
    
    while len(cleaned) > 1:
        # Берём с обоих концов
        if cleaned.popleft() != cleaned.pop():
            return False
    
    return True

print(is_palindrome_deque('A man, a plan, a canal: Panama'))  # True

6. С использованием recursion

def is_palindrome_recursive(s: str, left: int = 0, right: int = None) -> bool:
    if right is None:
        right = len(s) - 1
    
    # Пропускаем не-буквы
    while left < right and not s[left].isalnum():
        left += 1
    while left < right and not s[right].isalnum():
        right -= 1
    
    # Базовый случай
    if left >= right:
        return True
    
    # Проверяем и рекурсируем
    if s[left].lower() != s[right].lower():
        return False
    
    return is_palindrome_recursive(s, left + 1, right - 1)

print(is_palindrome_recursive('A man, a plan, a canal: Panama'))  # True

7. Для палиндромов чисел

def is_palindrome_number(n: int) -> bool:
    # Отрицательные числа не палиндромы
    if n < 0:
        return False
    
    # Метод 1: преобразование в строку
    s = str(n)
    return s == s[::-1]
    
    # Метод 2: математический подход
    # original = n
    # reversed_num = 0
    # while n > 0:
    #     reversed_num = reversed_num * 10 + n % 10
    #     n //= 10
    # return original == reversed_num

print(is_palindrome_number(121))      # True
print(is_palindrome_number(-121))     # False
print(is_palindrome_number(10))       # False

8. Для списков (общий случай)

def is_palindrome_list(lst: list) -> bool:
    left = 0
    right = len(lst) - 1
    
    while left < right:
        if lst[left] != lst[right]:
            return False
        left += 1
        right -= 1
    
    return True

print(is_palindrome_list([1, 2, 3, 2, 1]))      # True
print(is_palindrome_list([1, 2, 2, 1]))         # True
print(is_palindrome_list([1, 2, 3, 4]))         # False

9. Тестирование производительности

import timeit

s = 'A man a plan a canal Panama' * 1000

# Простой метод
t1 = timeit.timeit(
    lambda: is_palindrome_simple(s),
    number=1000
)

# Оптимизированный метод
t2 = timeit.timeit(
    lambda: is_palindrome_optimized(s),
    number=1000
)

print(f'Simple: {t1:.4f}s')
print(f'Optimized: {t2:.4f}s')
# Результат: optimized примерно в 1.5-2x быстрее

10. На собеседовании: что важно

Вопросы, которые зададут:

• Что считается палиндромом? (только буквы/цифры?)
• Важен ли регистр? (A != a?)
• Нужна ли оптимизация памяти?
• Какая временная сложность?

Правильные ответы:

# Для LeetCode задачи
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Вариант 1: простой (если не критична память)
        cleaned = ''.join(
            c.lower() for c in s if c.isalnum()
        )
        return cleaned == cleaned[::-1]  # O(n) time, O(n) space
        
        # Вариант 2: оптимальный (если критична память)
        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  # O(n) time, O(1) space

Сравнение подходов

На собеседовании: начни с простого, потом покажи оптимизацию, если спросят.