Ищем палиндромы: задача с собеседования 

Палиндром — это число, буквосочетание, слово или текст, одинаково читающееся в обоих направлениях.

Например: казак, потоп, дед

Часто на собеседованиях на этапе лайфкодинга просят написать простенький метод для поиска слов - палиндромов.

Вот пример такого метода:

def palindrome(*, a: str) -> bool:
    return a == a[::-1]

Пример использования:

>>> palindrome(a="коза")
>>> False
>>> palindrome(a="дед")
>>> True

В Python, выражение a[::-1] используется для получения обратной копии списка или строки. Это слайсинг-синтаксис, где:

a — список или строка, к которой применяется слайсинг.

: — синтаксис слайсинга (оставляем начало и конец пустыми, что означает, что берется вся строка или список).

-1 — шаг (если шаг отрицательный, то слайсинг идет в обратном порядке).

a[::-1] создаёт новую строку или список, содержащие те же элементы, что и оригинал, но в обратном порядке.

Есть еще один способ решения задачи:

def palindrome(*, a: str) -> bool:
    for i in range(len(a) // 2):
    	if x[i] != x[-i]:
            return False
    return True

Суть заключается в том, чтобы запустить цикл до половины слова и проверять с конца буквы срезом x[i] != x[-i]

Усложним немного задачу

на вход будет даваться не 1 слово, а целая фраза.

Например: Нажал кабан на баклажан!

В этом случае нам необходимо отсечь вхождения знаков препинания и пробелы, иногда допустимы цифры. Здесь тоже можно попробовать решить нашу задачу несколькими способами

import re

def palindrome_1(*, a: str) -> bool:
	cleaned_data = re.sub(r'[^a-zA-Z0-9]', '', a).lower()
    return cleaned_data == cleaned_data[::-1]

Объяснение palindrome_1

Здесь все тоже самое, как и в предыдущем способе, за исключением использования регулярного выражения:

re.sub() - используем функцию для замены подстрок, соответствующих шаблону

r'[^a-zA-Z0-9]- регулярное выражение (шаблон), означает "любой символ, который не является буквой или цифрой"

'' - это вторая часть re.sub(). Это то, на что заменять

a -строка, в которой производится замена

lower() - полученный результат переводим в нижний регистр

А далее, известная нам уже проверка

Временная сложность: O(n)

Пространственная сложность: O(n)

def palindrome_2(*, a: str) -> bool:
    new_str = ''
        for item in a:
            if item.isalnum():
                new_str += item.lower()
        return new_str == new_str[::-1]

Объяснение palindrome_2

Тут мы решили пойти по другому и использовать метод isalnum()для проверки символов строки - являются ли они буквами или цифрами.

Так же, мы используем переменную new_str, где будет храниться результирующая строка. Прошу обратить внимание, что эта переменная будет постоянно обновляться (пересоздаваться), так как строки являются неизеняемым типом данных. Мы постоянно в цикле будем создавать новую строку, копируя содержимое new_str и добавляя новый символ.

Так как это происходит внутри цикла, общая сложность этой части может быть O(n^2). Однако, интерпретаторы Python часто оптимизируют эту операцию, используя amortized analysis. На практике, если строки небольшие, различия в производительности с решением O(n) могут быть незначительными

Временная сложность:

Официально O(n^2), но на практике часто ближе к O(n) благодаря оптимизациям интерпретатора. Важно помнить о потенциальной квадратичной сложности, если код будет обрабатывать очень большие строки. Это нужно помнить, предлагая такой вариант решения

Пространственная сложность: O(n)

А что если я скажу, что есть еще один способ решения данной задачи, причем временная сложность будет O(n), а пространственная O(1)? Мало того, не нужно будет использовать регулярные выражения.

def palindrome_3(*, a: str) -> bool:
        l, r = 0, len(a) - 1

        while l < r:
            while l < r and not is_alpnum(ch=a[l]):
                l += 1
            while r > l and not is_alpnum(ch=a[r]):
                r -= 1
            if a[l].lower() != a[r].lower():
                return False
            l, r = l + 1, r - 1
        return True
    
def is_alpnum(*, ch):
    return ord('A') <= ord(ch) <= ord('Z') or ord('a') <= ord(ch) <= ord('z') or ord('0') <= ord(ch) <= ord('9')

Выглядит сложным? Погнали разбираться:

Объяснение palindrome_3

Для удобства мы реализовали функцию is_alpnum(). Она проверяет, является ли символ ch буквенно-цифровым (буквой латинского алфавита или цифрой).

ord(ch)- возвращает Unicode код символа ch. То есть мы проверяем, находится ли символ ch в диапазоне заглавных букв, в диапазоне строчных букв и в диапазоне цифр

Как работает основная функция palindrome_3:

l, r = 0, len(a) - 1 - инициализируем два указателя: l (левый) в начале строки и r (правый) в конце строки.

while l < r: - основной цикл, который продолжается, пока левый указатель не пересечет правый.

while l < r and not is_alpnum(ch=a[l]): l += 1- двигаем левый указатель вправо, пока не найдем буквенно-цифровой символ. not is_alpnum(ch=a[l]) проверяет, что символ не является буквенно-цифровым.

while r > l and not is_alpnum(ch=a[r]): r -= 1 - двигаем правый указатель влево, пока не найдем буквенно-цифровой символ.

if a[l].lower() != a[r].lower(): return False- если символы, на которые указывают l и r (приведенные к нижнему регистру), не равны, строка не является палиндромом, и функция возвращает False.

l, r = l + 1, r - 1- двигаем левый указатель вправо и правый указатель влево.

return True - если цикл завершился без нахождения несовпадений, строка является палиндромом, и функция возвращает True.

Как итог:

Временная сложность: O(n)

Пространственная сложность: O(1)