Lengste palindromiske delsekvens og delstreng
Bruk intervall-DP til å finne den lengste palindromiske delsekvensen, og bruk trikset med å utvide rundt sentrum for å finne den lengste palindromiske delstrengen.
Lengste palindromiske delsekvens og delstreng er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 2 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Palindromdefinisjoner på nytt
En palindromisk delsekvens er en delsekvens (elementene trenger ikke å være sammenhengende) som leses likt forlengs og baklengs. En palindromisk delstreng krever sammenhengende tegn. For 'bbbab' er den lengste palindromiske delsekvensen 'bbbb' (lengde 4), mens den lengste palindromiske delstrengen er 'bbb' (lengde 3). Disse to problemene krever ulike teknikker, selv om navnene ligner.
Lengste palindromiske delsekvens: LPS-tilstanden
Definer dp[i][j] som lengden på den lengste palindromiske delsekvensen i s[i..j]. Rekurrensen er: Hvis s[i] == s[j], er dp[i][j] = dp[i+1][j-1] + 2 (de to samsvarende tegnene utvider det indre palindromet). Ellers er dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (hopp over tegnet til venstre eller høyre). Basistilfelle: dp[i][i] = 1 for alle enkeltttegn.
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-fyllingsrekkefølge og implementasjon
Vi fyller ut LPS-tabellen i økende intervallengde, etter samme mønster som generell intervall-DP. For hvert intervall [i, j] med lengde 2 eller mer sjekker vi om de to grensetegnene samsvarer, og bruker rekurrensen. Det endelige svaret er dp[0][n-1], LPS-en for hele strengen.
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 via LCS-ekvivalens
Et elegant alternativ: LPS-en til strengen s er lik LCS-en til s og den reverserte strengen s[::-1]. Dette skyldes at enhver palindromisk delsekvens av s er en felles delsekvens av s og den reverserte strengen. Denne reduksjonen lar deg bruke LCS-koden din direkte på nytt. For 'bbbab' er den reverserte strengen 'babbb', og LCS-en deres er 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')) # 4Lengste palindromiske delstreng: brute force
Den lengste palindromiske delstrengen krever sammenhengende tegn. En brute force-tilnærming sjekker alle O(n²) delstrenger og verifiserer hver av dem på O(n) tid – totalt O(n³). Det finnes to raskere tilnærminger: intervall-DP på O(n²) tid og plass, og utvidelse rundt sentrum på O(n²) tid, men O(1) plass. I intervjuer foretrekkes utvidelse rundt sentrum fordi metoden har en mindre konstant og renere kode.
Intervall-DP for palindromisk delstreng
Definer dp[i][j] = True hvis s[i..j] er et palindrom. Rekurrens: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Basistilfeller: dp[i][i] = True og dp[i][i+1] = (s[i] == s[i+1]). Hold oversikt over det lengste palindromet som er funnet. Fyll ut i økende lengderekkefølge. Dette kjører på O(n²) tid og bruker O(n²) plass.
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'Teknikken med utvidelse rundt sentrum
Tilnærmingen med utvidelse rundt sentrum prøver hvert tegn (og hvert par av tilstøtende tegn) som et mulig palindromsenter og utvider utover så lenge begge sidene samsvarer. Det finnes 2n-1 mulige sentre (n for palindromer med oddetall lengde og n-1 for palindromer med partallslengde). Hver utvidelse tar høyst O(n) tid, noe som gir O(n²) totalt med O(1) plass – optimalt i de fleste intervjusituasjoner.
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'Plassoptimalisering for LPS
Intervall-DP for LPS bruker O(n²) plass. Når du bare trenger lengden (ikke selve delsekvensen), kan du redusere plassforbruket ved å observere at dp[i][j] bare avhenger av dp[i+1][j-1], dp[i+1][j] og dp[i][j-1]. Ved å bruke rader på nytt og lagre én diagonalverdi kan du oppnå O(n) plass – implementasjonen blir imidlertid mer kompleks, og dette kreves sjelden i intervjuer.
Gjenoppretting av LPS
For å gjenopprette den faktiske palindromiske delsekvensen må du gå bakover gjennom DP-tabellen. Start ved (0, n-1). Hvis s[i] == s[j], legger du tegnet til i begge ender av resultatet og går videre til (i+1, j-1). Ellers går du til den av (i+1, j) og (i, j-1) som har den største verdien. Denne grådige tilbakesporingen gjenoppretter entydig én optimal palindromisk delsekvens.
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')Sammenligning av tidskompleksiteten til LPS og LCS
Både LPS med intervall-DP og LCS kjører på O(n²) tid og bruker O(n²) plass. Utvidelse rundt sentrum for den lengste palindromiske delstrengen bruker O(n²) tid, men bare O(1) plass. Manachers algoritme løser delstrengproblemet på O(n) tid og plass, men den er så kompleks at intervjuere sjelden forventer den. I de fleste intervjusituasjoner er utvidelse rundt sentrum den forventede optimale løsningen for delstrengvarianten.
Vanlige fallgruver og kanttilfeller
Vær oppmerksom på disse fallgruvene: (1) å forveksle delsekvens med delstreng — dette er ulike problemer med ulike løsninger; (2) basistilfellet i intervall-DP-en for intervaller med lengde 2 krever særskilt behandling, siden dp[i+1][j-1] ville vært dp[i+1][i] (tomt intervall); (3) ved utvidelse rundt sentrum må De initialisere max_len = 1 (hvert enkelt tegn er et palindrom); og (4) når De henter ut resultatet, må De beregne start = i - (best-1)//2 for å finne startindeksen korrekt ut fra sentrum.
Hurtigsjekk
Test forståelsen Deres av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Leksjonsoppsummering
I denne leksjonen lærte De: LPS bruker intervall-DP med rekurrensen dp[i][j] = dp[i+1][j-1]+2 når tegnene samsvarer, det lengste palindromiske delstrenget løses best med utvidelse rundt sentrum på O(n²) tid og med O(1) plass, og LPS er lik LCS av strengen og den reverserte strengen. I neste leksjon tar vi for oss palindromisk partisjonering II, som kombinerer en palindromtabell med 1D-DP for å finne minimum antall kutt.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Lengste palindromiske delsekvens og delstreng» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Lengste palindromiske delsekvens og delstreng», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Lengste palindromiske delsekvens og delstreng»?
Bruk intervall-DP til å finne den lengste palindromiske delsekvensen, og bruk trikset med å utvide rundt sentrum for å finne den lengste palindromiske delstrengen. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Lengste palindromiske delsekvens og delstreng»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Intervall-DP-mønster og utfyllingsrekkefølge
- Lengste palindromiske delsekvens og delstreng
- Palindrom-partisjonering II
- Burst Balloons: Intervall-DP baklengs