Наибольшая палиндромная подпоследовательность и подстрока
Примените интервальный DP для поиска наибольшей палиндромной подпоследовательности и приём расширения вокруг центра для поиска наибольшей палиндромной подстроки
«Наибольшая палиндромная подпоследовательность и подстрока» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Повторение определений палиндрома
Палиндромная подпоследовательность — это подпоследовательность (элементы не обязательно идут подряд), которая одинаково читается слева направо и справа налево. Для палиндромной подстроки символы должны идти подряд. Для 'bbbab' самая длинная палиндромная подпоследовательность — 'bbbb' (длина 4), а самая длинная палиндромная подстрока — 'bbb' (длина 3). Эти две задачи требуют разных методов, несмотря на похожие названия.
Состояние LPS: самая длинная палиндромная подпоследовательность
Определим dp[i][j] как длину самой длинной палиндромной подпоследовательности в s[i..j]. Рекуррентное соотношение таково: если s[i] == s[j], то dp[i][j] = dp[i+1][j-1] + 2 (два совпадающих символа расширяют внутренний палиндром). В противном случае dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (пропускаем левый или правый символ). Базовый случай: dp[i][i] = 1 для каждого отдельного символа.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')Порядок заполнения и реализация LPS
Мы заполняем таблицу LPS в порядке возрастания длины интервала, как и в общем DP по интервалам. Для каждого интервала [i, j] длиной не менее 2 проверяем, совпадают ли два граничных символа, и применяем рекуррентное соотношение. Итоговый ответ — dp[0][n-1], то есть LPS всей строки.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4Эквивалентность LPS и LCS
Элегантная альтернатива: значение LPS для строки s равно значению LCS для s и её разворота s[::-1]. Это верно, поскольку любая палиндромная подпоследовательность s является общей подпоследовательностью s и её разворота. Такое преобразование позволяет напрямую использовать уже написанный код LCS. Для 'bbbab' разворотом будет 'babbb', а их LCS равна 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4Самая длинная палиндромная подстрока: полный перебор
Для самой длинной палиндромной подстроки символы должны идти подряд. Подход с полным перебором проверяет все подстроки — O(n²) — и каждую из них за O(n), что в сумме даёт O(n³). Существуют два более быстрых подхода: DP по интервалам за O(n²) по времени и памяти и расширение от центра за O(n²) по времени, но O(1) по памяти. На собеседованиях предпочтителен метод расширения от центра, поскольку у него меньшая константа и более простой код.
DP по интервалам для палиндромной подстроки
Определим dp[i][j] = True, если s[i..j] является палиндромом. Рекуррентное соотношение: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Базовые случаи: dp[i][i] = True и dp[i][i+1] = (s[i] == s[i+1]). Отслеживайте найденный палиндром максимальной длины. Заполняйте таблицу в порядке возрастания длины. Время работы — O(n²), память — O(n²).
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Метод расширения от центра
Подход с расширением от центра рассматривает каждый символ (а также каждую пару соседних символов) как потенциальный центр палиндрома и расширяется наружу, пока символы по обе стороны совпадают. Всего существует 2n-1 возможных центров: n центров палиндромов нечётной длины и n-1 — чётной. Каждое расширение занимает не более O(n) времени, поэтому общая сложность составляет O(n²) при памяти O(1) — это оптимальный вариант для большинства собеседований.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'Оптимизация памяти LPS
DP по интервалам для LPS использует память O(n²). Если Вам нужна только длина, а не сама подпоследовательность, память можно сократить, поскольку dp[i][j] зависит только от dp[i+1][j-1], dp[i+1][j] и dp[i][j-1]. Повторно используя строки и сохраняя одно диагональное значение, можно добиться памяти O(n), хотя реализация станет сложнее и на собеседованиях это требуется редко.
Восстановление LPS
Чтобы восстановить фактическую палиндромную подпоследовательность, проследите обратный путь по таблице DP. Начните с (0, n-1). Если s[i] == s[j], добавьте этот символ к обоим концам результата и перейдите к (i+1, j-1). В противном случае перейдите к тому из (i+1, j) и (i, j-1), где значение больше. Такое жадное обратное восстановление позволяет получить одну из оптимальных палиндромных подпоследовательностей.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')Сравнение временной сложности LPS и LCS
И DP по интервалам для LPS, и LCS работают за O(n²) времени и используют O(n²) памяти. Расширение от центра для самой длинной палиндромной подстроки работает за O(n²) времени, но использует только O(1) памяти. Алгоритм Манакера решает задачу о подстроке за O(n) времени и памяти, но он достаточно сложен, поэтому интервьюеры редко ожидают его применения. В большинстве случаев на собеседовании ожидаемым оптимальным решением для варианта с подстрокой будет расширение от центра.
Распространённые ошибки и крайние случаи
Обратите внимание на следующие подводные камни: (1) путаница между подпоследовательностью и подстрокой — это разные задачи с разными решениями; (2) базовый случай интервального DP для интервалов длины 2 требует особой обработки, поскольку dp[i+1][j-1] будет равно dp[i+1][i] (пустой интервал); (3) при расширении вокруг центра инициализируйте max_len = 1 (каждый отдельный символ является палиндромом); и (4) при извлечении результата вычисляйте start = i - (best-1)//2, чтобы правильно определить начальный индекс по центру.
Быстрая проверка
Проверьте, насколько вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», изученные на этом уроке.
Итоги урока
В этом уроке вы узнали: LPS использует интервальное DP с рекуррентным соотношением dp[i][j] = dp[i+1][j-1]+2, когда символы совпадают, длиннейшую палиндромную подстроку лучше всего искать с помощью расширения вокруг центра за время O(n²) и с использованием O(1) памяти, а также LPS равен LCS строки и её разворота. Далее мы рассмотрим задачу о разбиении на палиндромы II, которая объединяет таблицу палиндромов с одномерным DP для поиска минимального числа разрезов.
Часто задаваемые вопросы
Урок «Наибольшая палиндромная подпоследовательность и подстрока» бесплатный?
Да — полный текст урока «Наибольшая палиндромная подпоследовательность и подстрока» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Наибольшая палиндромная подпоследовательность и подстрока»?
Примените интервальный DP для поиска наибольшей палиндромной подпоследовательности и приём расширения вокруг центра для поиска наибольшей палиндромной подстроки Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Наибольшая палиндромная подпоследовательность и подстрока»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Шаблон интервального DP и порядок заполнения
- Наибольшая палиндромная подпоследовательность и подстрока
- Разбиение палиндрома II
- Взрыв шариков: интервальный DP в обратном порядке