Палиндром — это число, буквосочетание, слово или текст, одинаково читающееся в обоих направлениях.
Например: казак, потоп, дед
Часто на собеседованиях на этапе лайвкодинга просят написать простенький метод для поиска слов - палиндромов.
Вот пример такого метода:
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На вход будет даваться не 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.a[::-1] позволяет перевернуть строку за O(n) и сравнить с оригиналом. Это самый лаконичный способ проверки палиндрома в Python.palindrome_3) имеет временную сложность O(n) и пространственную O(1), что делает его самым оптимальным.
