Najdłuższy palindromiczny podciąg i podłańcuch
Stosować przedziałowe DP do znajdowania najdłuższego palindromicznego podciągu oraz sztuczkę rozszerzania wokół środka do znajdowania najdłuższego palindromicznego podłańcucha
Najdłuższy palindromiczny podciąg i podłańcuch to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Ponowne omówienie definicji palindromu
Palindromiczny podciąg to podciąg (którego elementy nie muszą występować obok siebie), który czyta się tak samo od przodu i od tyłu. Palindromiczny podłańcuch wymaga występowania sąsiadujących znaków. Dla 'bbbab' najdłuższym palindromicznym podciągiem jest 'bbbb' (długość 4), natomiast najdłuższym palindromicznym podłańcuchem jest 'bbb' (długość 3). Te dwa problemy, mimo podobnych nazw, wymagają różnych technik.
Najdłuższy palindromiczny podciąg: stan LPS
Definiujemy dp[i][j] jako długość najdłuższego palindromicznego podciągu w s[i..j]. Zależność rekurencyjna jest następująca: jeśli s[i] == s[j], to dp[i][j] = dp[i+1][j-1] + 2 (dwa pasujące znaki wydłużają wewnętrzny palindrom). W przeciwnym razie dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (pomijamy lewy albo prawy znak). Przypadek bazowy: dp[i][i] = 1 dla każdego pojedynczego znaku.
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')Kolejność wypełniania i implementacja LPS
Tabelę LPS wypełniamy według rosnącej długości przedziału, zgodnie z tym samym wzorcem co w ogólnym DP przedziałowym. Dla każdego przedziału [i, j] o długości co najmniej 2 sprawdzamy, czy oba znaki graniczne są takie same, i stosujemy zależność rekurencyjną. Ostateczną odpowiedzią jest dp[0][n-1], czyli LPS całego ciągu znaków.
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')) # 4LPS jako równoważność z LCS
Elegancka alternatywa: LPS ciągu s jest równe LCS ciągu s i jego odwrócenia s[::-1]. Wynika to z faktu, że każdy palindromiczny podciąg s jest wspólnym podciągiem s i jego odwrócenia. Dzięki temu przekształceniu można bezpośrednio ponownie wykorzystać kod LCS. Po odwróceniu 'bbbab' otrzymujemy 'babbb', a ich LCS ma długość 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')) # 4Najdłuższy palindromiczny podłańcuch: metoda siłowa
Najdłuższy palindromiczny podłańcuch wymaga sąsiadujących znaków. Podejście siłowe sprawdza wszystkie O(n²) podłańcuchy i weryfikuje każdy z nich w czasie O(n), co łącznie daje O(n³). Istnieją dwa szybsze podejścia: DP przedziałowe o czasie i pamięci O(n²) oraz rozszerzanie od środka o czasie O(n²), ale pamięci O(1). Podczas rozmów kwalifikacyjnych preferowane jest rozszerzanie od środka, ponieważ ma młą stałą i prostszy kod.
DP przedziałowe dla palindromicznego podłańcucha
Definiujemy dp[i][j] = True, jeśli s[i..j] jest palindromem. Zależność rekurencyjna: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Przypadki bazowe: dp[i][i] = True oraz dp[i][i+1] = (s[i] == s[i+1]). Śledzimy palindrom o największej znalezionej długości. Tabelę wypełniamy według rosnącej długości. Algorytm działa w czasie O(n²) i zużywa O(n²) pamięci.
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'Technika rozszerzania od środka
Podejście rozszerzania od środka traktuje każdy znak (a także każdą parę sąsiednich znaków) jako potencjalny środek palindromu i rozszerza się na zewnątrz, dopóki znaki po obu stronach są takie same. Istnieje 2n-1 możliwych środków (n dla palindromów o nieparzystej długości oraz n-1 dla palindromów o parzystej długości). Każde rozszerzanie zajmuje co najwyżej O(n) czasu, co daje łącznie O(n²) przy użyciu O(1) pamięci — jest to rozwiązanie optymalne w większości sytuacji podczas rozmów kwalifikacyjnych.
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'Optymalizacja pamięci LPS
DP przedziałowe dla LPS wykorzystuje O(n²) pamięci. Jeśli potrzebujesz tylko długości (a nie rzeczywistego podciągu), możesz zmniejszyć zużycie pamięci, zauważając, że dp[i][j] zależy wyłącznie od dp[i+1][j-1], dp[i+1][j] oraz dp[i][j-1]. Ponownie wykorzystując wiersze i zapisując jedną wartość na przekątnej, można osiągnąć zużycie O(n) pamięci — implementacja jest jednak bardziej złożona i rzadko wymaga się jej podczas rozmów kwalifikacyjnych.
Odtwarzanie LPS
Aby odtworzyć rzeczywisty palindromiczny podciąg, należy cofnąć się po tabeli DP. Zaczynamy od (0, n-1). Jeśli s[i] == s[j], dodajemy ten znak na obu końcach wyniku i przechodzimy do (i+1, j-1). W przeciwnym razie przechodzimy do tego z (i+1, j) lub (i, j-1), który ma większą wartość. Takie zachłanne odtwarzanie pozwala jednoznacznie odzyskać jedno z optymalnych rozwiązań w postaci palindromicznego podciągu.
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')Porównanie złożoności czasowej LPS i LCS
Zarówno LPS obliczane za pomocą DP przedziałowego, jak i LCS działają w czasie O(n²) i zużywają O(n²) pamięci. Rozszerzanie od środka dla najdłuższego palindromicznego podłańcucha działa w czasie O(n²), ale zużywa tylko O(1) pamięci. Algorytm Manachera rozwiązuje problem podłańcucha w czasie O(n) i przy użyciu O(n) pamięci, ale jest na tyle złożony, że rekruterzy rzadko go wymagają. W większości sytuacji podczas rozmów kwalifikacyjnych oczekiwanym optymalnym rozwiązaniem dla wariantu z podłańcuchem jest rozszerzanie od środka.
Typowe pułapki i przypadki brzegowe
Należy uważać na następujące pułapki: (1) mylenie podciągu z podłańcuchem — są to różne problemy, wymagające różnych rozwiązań; (2) przypadek bazowy programowania dynamicznego na przedziałach dla przedziałów długości 2 wymaga specjalnej obsługi, ponieważ dp[i+1][j-1] przyjmuje postać dp[i+1][i] (pusty przedział); (3) w przypadku rozszerzania wokół środka zainicjalizuj max_len = 1 (każdy pojedynczy znak jest palindromem); oraz (4) podczas wyodrębniania wyniku oblicz start = i - (best-1)//2, aby poprawnie znaleźć indeks początkowy na podstawie środka.
Szybki test
Sprawdź swoje zrozumienie koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: LPS wykorzystuje programowanie dynamiczne na przedziałach z rekurencją dp[i][j] = dp[i+1][j-1]+2, gdy znaki są takie same, najdłuższy palindromiczny podłańcuch najlepiej znaleźć metodą rozszerzania wokół środka w czasie O(n²) i przy użyciu O(1) pamięci oraz LPS jest równe LCS łańcucha i jego odwrócenia. W następnej lekcji zajmiemy się problemem dzielenia łańcucha na palindromy II, który łączy tabelę palindromów z jednowymiarowym DP do znajdowania minimalnej liczby cięć.
Często zadawane pytania
Czy lekcja „Najdłuższy palindromiczny podciąg i podłańcuch” jest bezpłatna?
Tak — pełny tekst „Najdłuższy palindromiczny podciąg i podłańcuch” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Najdłuższy palindromiczny podciąg i podłańcuch”?
Stosować przedziałowe DP do znajdowania najdłuższego palindromicznego podciągu oraz sztuczkę rozszerzania wokół środka do znajdowania najdłuższego palindromicznego podłańcucha Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Najdłuższy palindromiczny podciąg i podłańcuch”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Schemat przedziałowego DP i kolejność wypełniania
- Najdłuższy palindromiczny podciąg i podłańcuch
- Dzielenie palindromu II
- Burst Balloons: odwrócone przedziałowe DP