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

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

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

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

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

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]

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

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

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

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

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

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

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

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]

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

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

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

Официально O(n^2), но на практике часто ближе к 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.

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

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

Объяснение palindrome_1

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

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

Объяснение palindrome_2

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

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

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

Как итог:

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

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