Sottosequenza comune più lunga
Definisca la ricorrenza LCS per due stringhe, compili la tabella 2D e ricostruisca la sottosequenza effettiva ripercorrendo la tabella a ritroso
Sottosequenza comune più lunga è una lezione Coding 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è una sottosequenza?
Una sottosequenza di una stringa si forma eliminando alcuni caratteri (o nessuno) senza modificare l'ordine dei caratteri rimanenti. Ad esempio, 'ACE' è una sottosequenza di 'ABCDE', ma 'AEC' non lo è (l'ordine non è rispettato). La sottosequenza comune più lunga (LCS) di due stringhe è la sottosequenza più lunga che compare in entrambe. 'ABCBDAB' e 'BDCABA' hanno in comune la LCS 'BCBA' o 'BDAB', di lunghezza 4.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueDerivazione della ricorrenza LCS
Si definisca dp[i][j] come la lunghezza della LCS di text1[:i] e text2[:j]. Se i caratteri coincidono (text1[i-1] == text2[j-1]), si estende la LCS di 1: dp[i][j] = dp[i-1][j-1] + 1. Se non coincidono, si sceglie il risultato migliore ignorando un carattere dell'una o dell'altra stringa: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Caso base: dp[0][j] = dp[i][0] = 0 (la LCS con una stringa vuota ha lunghezza 0).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2Tracciamento della tabella LCS
Per text1='ABCD' e text2='ACBD': si comincia con tutti zeri. Quando i caratteri coincidono (A-A, C-C, B-B se si trovano nella posizione corretta, D-D), dp[i][j] = dp[i-1][j-1] + 1. Altrimenti si prende il massimo tra i vicini a sinistra e sopra. Scorrendo la tabella compilata, si vede come i passaggi diagonali corrispondano ai caratteri coincidenti. Il valore finale dp[4][4] fornisce la lunghezza della LCS.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Ricostruzione della LCS effettiva
Per recuperare la stringa LCS effettiva, percorra a ritroso la tabella DP a partire da dp[m][n]. Se text1[i-1] == text2[j-1], questo carattere appartiene alla LCS: lo registri e si sposti diagonalmente verso (i-1, j-1). Se dp[i-1][j] > dp[i][j-1], si sposti verso l’alto; altrimenti verso sinistra. Alla fine, inverta i caratteri raccolti, poiché la percorrenza è stata effettuata a ritroso. Questa ricostruzione richiede O(m+n) tempo.
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABOttimizzazione dello spazio fino a O(n)
La tabella LCS necessita solo della riga corrente e di quella precedente. Può usare un array 1D di dimensione n+1 e una variabile diagonal per memorizzare il valore che si trovava in dp[i-1][j-1] prima che venisse sovrascritto. Scorra ogni riga da sinistra a destra. Dopo ogni cella, il valore aggiornato di dp[j] contiene il valore della riga corrente; salvi il valore precedente in diagonal prima di sovrascriverlo.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4Relazione tra LCS e distanza di modifica
La LCS è strettamente correlata alla distanza di modifica (distanza di Levenshtein). Se conosce la LCS, può calcolare la distanza di modifica minima usando solo inserimenti e cancellazioni: edit_dist = m + n - 2 * LCS(s1, s2). Ogni carattere di s1 che non appartiene alla LCS richiede una cancellazione e ogni carattere di s2 che non appartiene alla LCS richiede un inserimento. Qui la sostituzione non viene conteggiata, perché sono consentite solo operazioni di inserimento e cancellazione, ma questa formula è utile per problemi correlati.
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[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]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5Operazione di cancellazione per due stringhe
Operazione di cancellazione per due stringhe (LeetCode 583) chiede il numero minimo di cancellazioni necessarie per rendere uguali due stringhe. I caratteri conservati devono formare una sottosequenza comune, quindi bisogna massimizzare la LCS e cancellare tutto il resto. Risposta: m + n - 2 * LCS(s1, s2). Questo equivale alla distanza di modifica con sole operazioni di inserimento e cancellazione descritta sopra. Formulare i problemi in termini di LCS è una potente tecnica di riduzione.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4Sottostringa comune più lunga
Non confonda la LCS (sottosequenza) con la sottostringa comune più lunga. Una sottostringa è contigua, quindi quando i caratteri non corrispondono il conteggio viene reimpostato a 0, invece di scegliere il massimo tra i valori vicini. La ricorrenza cambia così: se i caratteri corrispondono, dp[i][j] = dp[i-1][j-1] + 1; altrimenti dp[i][j] = 0. Tenga traccia del valore massimo incontrato in tutte le celle.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)LCS per il confronto di sequenze
La LCS viene ampiamente utilizzata negli strumenti diff (come Unix diff) per confrontare i file. Lo script delle modifiche tra due file viene derivato dalla LCS: le righe presenti nella LCS non cambiano, le righe aggiuntive del file 1 vengono cancellate e quelle aggiuntive del file 2 vengono inserite. Comprendere la LCS aiuta a capire come i sistemi di controllo versione tracciano le modifiche e perché si verificano conflitti durante il merge.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)Supersequenza comune più breve
La supersequenza comune più breve (LeetCode 1092) richiede la stringa più breve che contenga sia s1 sia s2 come sottosequenze. Qualsiasi carattere della LCS compare una sola volta nella supersequenza; i caratteri non appartenenti alla LCS presenti in entrambe le stringhe devono essere inclusi. Lunghezza = m + n - LCS(s1, s2). Per ricostruirla, usi lo stesso backtracking della LCS, includendo però i caratteri di entrambe le stringhe nelle posizioni in cui non corrispondono.
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5Complessità della LCS e consigli per i colloqui
L’algoritmo classico per la LCS richiede O(m×n) di tempo e O(m×n) di spazio; con la tecnica dell’array scorrevole, lo spazio può essere ridotto a O(min(m,n)). Consigli fondamentali per i colloqui: (1) definisca chiaramente il significato dello stato DP prima di scrivere il codice; (2) gestisca distintamente i casi di corrispondenza e di mancata corrispondenza; (3) quando le viene chiesto di ricostruire la sequenza, descriva il backtracking prima di implementarlo; (4) citi la Longest Increasing Subsequence (LIS) come problema 1D correlato, risolvibile in O(n log n) con il patience sorting.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: LCS uses dp[i][j] = dp[i-1][j-1]+1 on match, otherwise max(dp[i-1][j], dp[i][j-1]), la sequenza effettiva viene ricostruita percorrendo a ritroso la diagonale in caso di corrispondenza e andando verso il vicino più grande in caso di mancata corrispondenza e la LCS è alla base della distanza di modifica, delle operazioni di cancellazione, della supersequenza comune più breve e degli strumenti diff. Nella prossima lezione ricaveremo la ricorrenza della distanza di modifica (Levenshtein), che aggiunge le sostituzioni al modello della LCS.
Domande Frequenti
La lezione «Sottosequenza comune più lunga» è gratuita?
Sì — il testo completo di «Sottosequenza comune 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sottosequenza comune più lunga»?
Definisca la ricorrenza LCS per due stringhe, compili la tabella 2D e ricostruisca la sottosequenza effettiva ripercorrendo la tabella a ritroso Eserciti Coding 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding 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 comune 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 Coding Interview Prep?
Sì. Ogni lezione Coding 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
- Percorsi unici e somma minima dei percorsi nelle griglie
- Sottosequenza comune più lunga
- Distanza di modifica (Levenshtein)
- Ottimizzazione dello spazio per la DP 2D