Plus longue sous-séquence commune
Définissez la récurrence de LCS pour deux chaînes, remplissez le tableau 2D et reconstruisez la sous-séquence réelle en remontant dans le tableau.
Plus longue sous-séquence commune est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’une sous-séquence ?
Une sous-séquence d’une chaîne s’obtient en supprimant certains caractères (ou aucun) sans modifier l’ordre des caractères restants. Par exemple, « ACE » est une sous-séquence de « ABCDE », mais « AEC » ne l’est pas (l’ordre est incorrect). La sous-séquence commune la plus longue (LCS) de deux chaînes est la plus longue sous-séquence qui apparaît dans les deux. « ABCBDAB » et « BDCABA » ont en commun la LCS « BCBA » ou « BDAB », de longueur 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)) # TrueDérivation de la récurrence de LCS
Définissez dp[i][j] comme la longueur de la LCS de text1[:i] et text2[:j]. Si les caractères correspondent (text1[i-1] == text2[j-1]), nous prolongeons la LCS de 1 : dp[i][j] = dp[i-1][j-1] + 1. S’ils ne correspondent pas, nous conservons la meilleure solution en ignorant un caractère de l’une ou l’autre chaîne : dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Cas de base : dp[0][j] = dp[i][0] = 0 (la LCS d’une chaîne vide a une longueur de 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')) # 2Parcourir le tableau de LCS
Pour text1='ABCD' et text2='ACBD' : commencez avec uniquement des zéros. Lorsque les caractères correspondent (A-A, C-C, B-B s’ils sont à la bonne position, D-D), dp[i][j] = dp[i-1][j-1] + 1. Sinon, prenez le maximum des cellules voisines de gauche et du dessus. La lecture du tableau rempli montre comment les déplacements diagonaux correspondent aux caractères qui se correspondent. La valeur finale dp[4][4] donne la longueur de la 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')Reconstruction de la chaîne LCS réelle
Pour retrouver la chaîne LCS réelle, remontez dans la table DP à partir de dp[m][n]. Si text1[i-1] == text2[j-1], ce caractère fait partie du LCS : enregistrez-le et déplacez-vous en diagonale vers (i-1, j-1). Si dp[i-1][j] > dp[i][j-1], déplacez-vous vers le haut ; sinon, déplacez-vous vers la gauche. Inversez les caractères collectés à la fin, puisque vous avez remonté la table. Cette reconstruction s’effectue en temps O(m+n).
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 BDABOptimisation de l’espace en O(n)
La table LCS nécessite uniquement la ligne actuelle et la ligne précédente. Vous pouvez utiliser un tableau 1D de taille n+1 ainsi qu’une variable diagonal pour stocker la valeur qui se trouvait à dp[i-1][j-1] avant d’être remplacée. Parcourez chaque ligne de gauche à droite. Après chaque cellule, la valeur mise à jour de dp[j] correspond à la valeur de la ligne actuelle, et vous enregistrez la valeur précédente dans diagonal avant de la remplacer.
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')) # 4Relation entre le LCS et la distance d’édition
Le LCS est étroitement lié à la distance d’édition (distance de Levenshtein). Si vous connaissez le LCS, vous pouvez calculer la distance d’édition minimale en utilisant uniquement des insertions et des suppressions : edit_dist = m + n - 2 * LCS(s1, s2). Chaque caractère de s1 qui ne figure pas dans le LCS nécessite une suppression, et chaque caractère de s2 qui n’y figure pas nécessite une insertion. La substitution n’est pas comptabilisée ici, puisque nous autorisons uniquement les insertions et les suppressions, mais cette formule est utile pour des problèmes connexes.
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')) # 5Opération de suppression pour deux chaînes
Opération de suppression pour deux chaînes (LeetCode 583) demande le nombre minimal de suppressions nécessaires pour rendre deux chaînes égales. Les caractères conservés doivent former une sous-séquence commune ; vous devez donc maximiser le LCS et supprimer tout le reste. Réponse : m + n - 2 * LCS(s1, s2). Cela équivaut à la distance d’édition avec insertions et suppressions présentée précédemment. Formuler les problèmes en termes de LCS constitue une puissante technique de réduction.
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')) # 4Plus longue sous-chaîne commune
Ne confondez pas le LCS (sous-séquence) avec la plus longue sous-chaîne commune. Une sous-chaîne est contiguë : lorsque les caractères ne correspondent pas, le compteur revient donc à 0 au lieu de prendre le maximum des voisins. La relation de récurrence devient la suivante : si les caractères correspondent, dp[i][j] = dp[i-1][j-1] + 1 ; sinon, dp[i][j] = 0. Suivez la valeur maximale observée parmi toutes les cellules.
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 pour la comparaison de séquences
Le LCS est largement utilisé dans les outils de comparaison (comme l’outil Unix diff) pour comparer des fichiers. Le script de modifications entre deux fichiers est dérivé du LCS : les lignes du LCS sont inchangées, les lignes supplémentaires du fichier 1 sont supprimées et les lignes supplémentaires du fichier 2 sont insérées. Comprendre le LCS vous aide à comprendre comment les systèmes de contrôle de version suivent les modifications et pourquoi des conflits de fusion se produisent.
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)Plus courte super-séquence commune
La plus courte super-séquence commune (LeetCode 1092) demande la chaîne la plus courte qui contient à la fois s1 et s2 comme sous-séquences. Chaque caractère du LCS apparaît une seule fois dans la super-séquence ; les caractères qui ne font pas partie du LCS dans les deux chaînes doivent être inclus. Longueur = m + n - LCS(s1, s2). Pour reconstruire la chaîne, utilisez la même remontée dans la table que pour le LCS, mais incluez les caractères des deux chaînes aux positions qui ne correspondent pas.
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 5Complexité du LCS et conseils pour les entretiens
L’algorithme classique du LCS s’exécute en temps O(m×n) et avec un espace O(m×n), une complexité spatiale qui peut être réduite à O(min(m,n)) grâce à l’astuce du tableau glissant. Conseils clés pour les entretiens : (1) définissez clairement ce que représente l’état DP avant de coder ; (2) traitez distinctement les cas de correspondance et de non-correspondance ; (3) lorsqu’on vous demande de reconstruire la séquence, décrivez la remontée dans la table avant de la coder ; (4) mentionnez la plus longue sous-séquence croissante (LIS) comme problème 1D connexe, résoluble en O(n log n) avec le tri par patience.
# 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)Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : le LCS utilise dp[i][j] = dp[i-1][j-1]+1 en cas de correspondance, et sinon max(dp[i-1][j], dp[i][j-1]), la séquence réelle se reconstruit en remontant en diagonale en cas de correspondance et vers le voisin le plus grand en cas de non-correspondance, et le LCS est à la base de la distance d’édition, des opérations de suppression, de la plus courte super-séquence commune et des outils de comparaison. Ensuite, nous déduirons la relation de récurrence de la distance d’édition (Levenshtein), qui ajoute les substitutions au cadre du LCS.
Questions Fréquemment Posées
La leçon « Plus longue sous-séquence commune » est-elle gratuite ?
Oui — le texte complet de « Plus longue sous-séquence commune » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Plus longue sous-séquence commune » ?
Définissez la récurrence de LCS pour deux chaînes, remplissez le tableau 2D et reconstruisez la sous-séquence réelle en remontant dans le tableau. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Plus longue sous-séquence commune » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Chemins uniques et somme minimale des chemins sur des grilles
- Plus longue sous-séquence commune
- Distance d’édition (Levenshtein)
- Optimisation de l’espace pour la DP 2D