Задача №3: Valid Palindrome

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

Примеры палиндромов: «‎радар»‎, «‎казак»‎, «‎12321»‎. В данной задаче нас интересуют фразы, которые могут содержать символы, не относящиеся к алфавитно-цифровым, и различные регистры букв.

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

Условие задачи

Дана строка s и необходимо вернуть true, если строка является палиндромом после преобразования, и false в противном случае.

Примеры:

1. Ввод: s = "A man, a plan, a canal: Panama"
   Вывод: true
   Объяснение: После удаления всех не алфавитно-цифровых символов и приведения к нижнему регистру получаем строку “amanaplanacanalpanama”, которая является палиндромом.
2. Ввод: s = "race a car"
   Вывод: false
   Объяснение: После преобразований получаем “raceacar”, что не является палиндромом.
3. Ввод: s = " "
   Вывод: true
   Объяснение: После удаления не алфавитно-цифровых символов строка становится пустой, а пустая строка является палиндромом.

Решение

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = ''.join(c.lower() for c in s if c.isalnum())
        return cleaned == cleaned[::-1]

Этот код является решением задачи на проверку палиндрома, описанной ранее. Давайте разберём его по шагам.

Шаг 1: Нормализация строки

cleaned = ''.join(c.lower() for c in s if c.isalnum())

создаёт новую строку cleaned, которая представляет собой нормализованную версию исходной строки s. Этот процесс включает в себя несколько шагов:

c.lower() for c in s: 

для каждого символа c в строке s преобразовывает его в нижний регистр. Это гарантирует, что все буквы будут сравниваться без учёта регистра.

if c.isalnum():

проверяет, является ли символ c алфавитно-цифровым (то есть либо буквой, либо цифрой). Если нет, символ исключается из результата.

''.join(...)

объединяет все отобранные и преобразованные символы в одну строку без каких-либо разделителей.

Шаг 2: Проверка на палиндром

return cleaned == cleaned[::-1]

возвращает True, если нормализованная строка cleaned является палиндромом, и False — в противном случае. Для этого сравнивается строка cleaned с её же перевёрнутой версией, полученной с помощью среза [::-1], который возвращает все элементы строки в обратном порядке. Если исходная и перевёрнутая строки идентичны, значит, исходная строка является палиндромом.

Временная сложность алгоритма – [math]O(n)[/math], где [math]n[/math] – количество элементов во входном массиве.