Теги: #python, #dynamic_programming, #string
🍻 Привет, зеркальные искатели! 🍻
Присаживайтесь, я заказал нам по кружечке. 🍺 Сегодня мы с вами затеем настоящее расследование в мире строк и символов. Вы когда-нибудь задумывались, что самая длинная палиндромная подстрока в строке — это как зеркальный коридор в лабиринте? Да-да, именно так! Сегодняшняя задачка как раз о том, как найти этот сокровенный коридор. 🕵️♂️
🔍 Что такое палиндром?
Если кто-то из вас, дорогие читатели, не в курсе, палиндром — это слово, число, фраза, другая последовательность символов или чисел, которая одинаково читается в обоих направлениях (если не считать пробелы, знаки препинания и регистр).
🎭 Тайна зеркального лабиринта
Вы когда-нибудь были в зеркальном лабиринте? Ходишь, ходишь и не можешь найти выход, а потом вдруг видишь отражение, которое как-то странно себя ведет. Вот и в строке нам нужно найти самую длинную такую “подстроку-отражение”, или палиндром.
📜 Что мы узнаем сегодня
- Как разобраться с лабиринтом строк и символов.
- Как найти идеальное отражение, не разбив зеркало.
Как обычно, полное условие задачи можно найти тут. Если вы готовы, держите свои кружки крепче, и поехали! 🍻🚀
Сквозь зеркала и туман: поймаем нашего палиндрома 🕵️♂️🔍
Шаг 1: Введем два указателя
Для начала, представьте, что у вас есть два указателя. Один будет двигаться вперёд, другой назад, как в танце по обе стороны зеркала. Эти указатели помогут нам определить, где начинается и заканчивается палиндром.
👉 Для новичков: Указатели — это просто индексы, показывающие положение символов в строке. Например, в строке "babad" первый символ "b" имеет индекс 0, а последний "d" имеет индекс 4.
left, right = 0, len(s) - 1
Шаг 2: Развернем палиндром во все стороны
Теперь, когда у нас есть начальная точка, попробуем "развернуть" палиндром в обе стороны, проверяя, совпадают ли символы. Если символы совпадают, двигаем указатели.
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
Шаг 3: Найдем самый длинный палиндром
Окей, у нас могут быть разные палиндромы, найденные в разных частях строки. Нам нужно выбрать самый длинный из них. Для этого будем сохранять каждый найденный палиндром и сравнивать его длину с предыдущим максимумом.
if len(longest) < right - left - 1:
longest = s[left + 1:right]
Финальный код: Собираем всё вместе 🛠️
class Solution:
def longestPalindrome(self, s: str) -> str:
# Инициализируем переменные для самого длинного палиндрома
longest = ""
for i in range(len(s)):
# От каждой точки пытаемся "развернуть" палиндром
for left, right in [(i, i), (i, i + 1)]:
# Пока символы совпадают, двигаем указатели
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# Если нашли более длинный палиндром, обновляем
if len(longest) < right - left - 1:
longest = s[left + 1:right]
return longest
Асимптотика 🤓
По поводу асимптотики, друзья мои, всё не так уж и плохо! Наш алгоритм работает за O(n²), что для такой таинственной задачи вполне норм! Хотите быстрее? Извините, у нас тут не квантовые компьютеры!
Альтернативные Решения 🔄
Можно было бы воспользоваться динамическим программированием или даже каким-нибудь суровым алгоритмом типа "Манакера", но тогда у нас не получится так красиво пройтись по лабиринту. И вам не будет так весело! 😜
Анекдот 🤣
Знаете, почему программисты не любят палиндромы? Потому что даже в зеркальном мире их код не работает!
🤯 Вы думали это всё? Не тут то было. Для самых стойких зазеркальцев кто не боится взрыва мозга самый лучший алгоритм для этой задачи! 🧠
Метод Манакера 🚀
Для тех, кто хочет решить эту задачу в самой лучшей асимптотике O(n), есть алгоритм Манакера. Этот метод в 100500 раз быстрее, чем мы делали раньше. Представьте, что это не просто зеркальный лабиринт, это зеркальный лабиринт с турбо-ускорителем!
Основная идея 🎭
Мы создаем новую строку, вставляя между каждым символом какой-либо не встречающийся символ (например, '#'). Это делается для того, чтобы одинаково обрабатывать палиндромы четной и нечетной длины.
Шаги решения ⚙️
- Преобразование строки: Добавим '#' между каждым символом строки и в начале и в конце.
- Инициализация: Создадим массив P той же длины, что и преобразованная строка. P[i] будет хранить радиус палиндрома с центром в i.
- Заполнение массива P: Используем два указателя, один для центра палиндрома, и один для его радиуса. Будем двигаться по строке и для каждого символа обновлять P и, соответственно, нашего "чемпиона" — самый длинный палиндром.
И сам код 💻
class Solution:
def longestPalindrome(self, s: str) -> str:
# Шаг 1: Преобразуем строку
T = '#'.join(s)
T = '#' + T + '#'
n = len(T)
P = [0] * n
C, R = 0, 0 # C - центр, R - радиус
for i in range(n):
# Зеркальный индекс относительно C
mirror = 2 * C - i
if R > i:
P[i] = min(R - i, P[mirror])
# Пытаемся расширить палиндром
a, b = i + (1 + P[i]), i - (1 + P[i])
while a < n and b >= 0 and T[a] == T[b]:
P[i] += 1
a += 1
b -= 1
# Обновляем C и R
if i + P[i] > R:
C, R = i, i + P[i]
# Находим самый длинный палиндром
max_len = max(P)
center = P.index(max_len)
return s[(center - max_len) // 2: (center + max_len) // 2]
Видели, как наш "турбо-ускоритель" сработал? С O(n²), до O(n) как ни в чем не бывало!
Если вы дошли до этого момента и не потерялись в зеркалах, вы — герой! 🦸♂️