Sottosequenza e sottostringa palindroma più lunga
Applichi la DP sugli intervalli per trovare la sottosequenza palindroma più lunga e il metodo dell'espansione attorno al centro per trovare la sottostringa palindroma più lunga.
Sottosequenza e sottostringa palindroma più lunga è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Definizioni dei palindromi: ripasso
Una sottosequenza palindromica è una sottosequenza (gli elementi non devono essere necessariamente contigui) che si legge allo stesso modo da sinistra a destra e viceversa. Una sottostringa palindromica richiede caratteri contigui. Per 'bbbab', la sottosequenza palindromica più lunga è 'bbbb' (lunghezza 4), mentre la sottostringa palindromica più lunga è 'bbb' (lunghezza 3). Questi due problemi richiedono tecniche diverse nonostante i nomi simili.
Sottosequenza palindromica più lunga: stato LPS
Definiamo dp[i][j] come la lunghezza della sottosequenza palindromica più lunga in s[i..j]. La ricorrenza è: se s[i] == s[j], allora dp[i][j] = dp[i+1][j-1] + 2 (i due caratteri uguali estendono il palindromo interno). Altrimenti, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (si ignora il carattere a sinistra oppure quello a destra). Caso base: dp[i][i] = 1 per ogni carattere singolo.
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')Ordine di riempimento e implementazione della LPS
Riempiamo la tabella LPS per lunghezze di intervallo crescenti, seguendo lo stesso schema della DP sugli intervalli generale. Per ogni intervallo [i, j] di lunghezza pari o superiore a 2, verifichiamo se i due caratteri agli estremi coincidono e applichiamo la ricorrenza. La risposta finale è dp[0][n-1], la LPS dell'intera stringa.
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 tramite l'equivalenza con la LCS
Un'alternativa elegante: la LPS della stringa s è uguale alla LCS di s e della sua inversa s[::-1]. Questo accade perché ogni sottosequenza palindromica di s è una sottosequenza comune di s e della sua inversa. Questa riduzione consente di riutilizzare direttamente il codice LCS. Per 'bbbab', la stringa inversa è 'babbb' e la loro LCS ha lunghezza 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')) # 4Sottostringa palindromica più lunga: forza bruta
La sottostringa palindromica più lunga richiede caratteri contigui. Un approccio di forza bruta esamina tutte le O(n²) sottostringhe e verifica ciascuna in O(n) di tempo, per un totale di O(n³). Esistono due approcci più veloci: la DP sugli intervalli in O(n²) di tempo e spazio e l'espansione dal centro verso l'esterno in O(n²) di tempo ma O(1) di spazio. Nei colloqui si preferisce l'espansione dal centro verso l'esterno perché ha una costante più contenuta e un codice più semplice.
DP sugli intervalli per la sottostringa palindromica
Definiamo dp[i][j] = True se s[i..j] è un palindromo. Ricorrenza: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Casi base: dp[i][i] = True e dp[i][i+1] = (s[i] == s[i+1]). Teniamo traccia del palindromo di lunghezza massima trovato. Riempiamo la tabella in ordine di lunghezza crescente. Questo approccio richiede O(n²) di tempo e O(n²) di spazio.
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'Tecnica di espansione dal centro verso l'esterno
L'approccio di espansione dal centro verso l'esterno prova ogni carattere (e ogni coppia di caratteri adiacenti) come possibile centro del palindromo ed espande verso l'esterno finché i caratteri sui due lati coincidono. Esistono 2n-1 centri possibili (n per le lunghezze dispari e n-1 per quelle pari). Ogni espansione richiede al massimo O(n) di tempo, per un totale di O(n²) con O(1) di spazio: è ottimale nella maggior parte dei colloqui.
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'Ottimizzazione dello spazio per la LPS
La DP sugli intervalli per la LPS usa O(n²) di spazio. Quando serve solo la lunghezza (non la sottosequenza effettiva), è possibile ridurre lo spazio osservando che dp[i][j] dipende solo da dp[i+1][j-1], dp[i+1][j] e dp[i][j-1]. Riutilizzando le righe e salvando un valore sulla diagonale, si può ottenere uno spazio O(n), anche se l'implementazione è più complessa e raramente necessaria nei colloqui.
Ricostruzione della LPS
Per ricostruire la sottosequenza palindromica effettiva, si ripercorre a ritroso la tabella DP. Si parte da (0, n-1). Se s[i] == s[j], si aggiunge quel carattere a entrambe le estremità del risultato e ci si sposta su (i+1, j-1). Altrimenti, ci si sposta su quello tra (i+1, j) e (i, j-1) che ha il valore maggiore. Questa ricostruzione a ritroso di tipo greedy recupera in modo univoco una sottosequenza palindromica ottimale.
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')Confronto della complessità temporale tra LPS e LCS
Sia la LPS tramite DP sugli intervalli sia la LCS richiedono O(n²) di tempo e O(n²) di spazio. L'espansione dal centro verso l'esterno per la sottostringa palindromica più lunga richiede O(n²) di tempo ma solo O(1) di spazio. L'algoritmo di Manacher risolve il problema della sottostringa in O(n) di tempo e spazio, ma è abbastanza complesso che gli intervistatori raramente se lo aspettino. Nella maggior parte dei colloqui, l'espansione dal centro verso l'esterno è la soluzione ottimale attesa per la variante delle sottostringhe.
Errori comuni e casi limite
Faccia attenzione a queste insidie: (1) confondere una sottosequenza con una sottostringa — sono problemi diversi, con soluzioni diverse; (2) il caso base della DP su intervalli per gli intervalli di lunghezza 2 richiede una gestione speciale, poiché dp[i+1][j-1] diventerebbe dp[i+1][i] (intervallo vuoto); (3) per l'espansione attorno al centro, inizializzi max_len = 1 (ogni singolo carattere è un palindromo); e (4) nell'estrarre il risultato, calcoli start = i - (best-1)//2 per individuare correttamente l'indice iniziale a partire dal centro.
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: LPS usa la DP su intervalli con la ricorrenza dp[i][j] = dp[i+1][j-1]+2 quando i caratteri coincidono, la sottostringa palindroma più lunga si risolve al meglio con l'espansione attorno al centro in O(n²) di tempo e O(1) di spazio e LPS equivale alla LCS della stringa e della sua inversa. Nel prossimo argomento affronteremo il problema del palindrome partitioning II, che combina una tabella dei palindromi con una DP 1D per trovare il numero minimo di tagli.
Domande Frequenti
La lezione «Sottosequenza e sottostringa palindroma più lunga» è gratuita?
Sì — il testo completo di «Sottosequenza e sottostringa palindroma più lunga» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sottosequenza e sottostringa palindroma più lunga»?
Applichi la DP sugli intervalli per trovare la sottosequenza palindroma più lunga e il metodo dell'espansione attorno al centro per trovare la sottostringa palindroma più lunga. Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Sottosequenza e sottostringa palindroma più lunga»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema della DP sugli intervalli e ordine di riempimento
- Sottosequenza e sottostringa palindroma più lunga
- Partizionamento palindromico II
- Burst Balloons: DP sugli intervalli al contrario