Subsecuencia común más larga
Defina la recurrencia de LCS para dos strings, rellene la tabla 2D y reconstruya la subsecuencia real retrocediendo por la tabla.
Subsecuencia común más larga es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué es una subsecuencia?
Una subsecuencia de una cadena se forma eliminando algunos caracteres (o ninguno) sin cambiar el orden de los caracteres restantes. Por ejemplo, 'ACE' es una subsecuencia de 'ABCDE', pero 'AEC' no lo es (el orden no se respeta). La subsecuencia común más larga (LCS) de dos cadenas es la subsecuencia más larga que aparece en ambas. 'ABCBDAB' y 'BDCABA' comparten la LCS 'BCBA' o 'BDAB', ambas de longitud 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)) # TrueDerivación de la recurrencia de LCS
Defina dp[i][j] como la longitud de la LCS de text1[:i] y text2[:j]. Si los caracteres coinciden (text1[i-1] == text2[j-1]), ampliamos la LCS en 1: dp[i][j] = dp[i-1][j-1] + 1. Si no coinciden, elegimos la mejor opción entre omitir un carácter de una u otra cadena: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Caso base: dp[0][j] = dp[i][0] = 0 (la LCS de una cadena vacía tiene longitud 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')) # 2Recorrido de la tabla de LCS
Para text1='ABCD' y text2='ACBD': comience con todos los valores a cero. Cuando los caracteres coinciden (A-A, C-C, B-B si están en la posición correcta, D-D), dp[i][j] = dp[i-1][j-1] + 1. En caso contrario, tome el máximo de los vecinos izquierdo y superior. Al recorrer la tabla completa se observa cómo los pasos diagonales corresponden a los caracteres coincidentes. El valor final dp[4][4] proporciona la longitud 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')Reconstrucción de la LCS real
Para recuperar la cadena LCS real, recorra hacia atrás la tabla de DP desde dp[m][n]. Si text1[i-1] == text2[j-1], este carácter forma parte de la LCS: regístrelo y muévase en diagonal hasta (i-1, j-1). Si dp[i-1][j] > dp[i][j-1], muévase hacia arriba; de lo contrario, hacia la izquierda. Invierta los caracteres recopilados al final, ya que ha recorrido la tabla hacia atrás. Esta reconstrucción se ejecuta en tiempo 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 BDABOptimización del espacio a O(n)
La tabla de LCS solo necesita la fila actual y la anterior. Puede usar un arreglo unidimensional de tamaño n+1 y una variable diagonal para almacenar el valor que estaba en dp[i-1][j-1] antes de sobrescribirse. Recorra cada fila de izquierda a derecha. Después de cada celda, el dp[j] actualizado contiene el valor de la fila actual, y debe guardar el valor anterior en diagonal antes de sobrescribirlo.
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')) # 4Relación entre la LCS y la distancia de edición
La LCS está estrechamente relacionada con la distancia de edición (distancia de Levenshtein). Si conoce la LCS, puede calcular la distancia de edición mínima usando únicamente inserciones y eliminaciones: edit_dist = m + n - 2 * LCS(s1, s2). Cada carácter de s1 que no está en la LCS requiere una eliminación, y cada carácter de s2 que no está en la LCS requiere una inserción. Aquí no se cuenta la sustitución, ya que solo permitimos inserciones y eliminaciones, pero esta fórmula resulta útil para problemas relacionados.
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')) # 5Operación de eliminación para dos cadenas
La operación de eliminación para dos cadenas (LeetCode 583) solicita el número mínimo de eliminaciones necesarias para hacer iguales dos cadenas. Los caracteres que conserva deben formar una subsecuencia común, por lo que debe maximizar la LCS y eliminar todo lo demás. Respuesta: m + n - 2 * LCS(s1, s2). Esto equivale a la distancia de edición con inserciones y eliminaciones anterior. Plantear los problemas en términos de LCS es una potente técnica de reducción.
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')) # 4Subcadena común más larga
No confunda la LCS (subsecuencia) con la subcadena común más larga. Una subcadena es contigua, por lo que, si los caracteres no coinciden, el conteo se restablece a 0 en lugar de tomar el máximo de los vecinos. La recurrencia cambia a: si los caracteres coinciden, dp[i][j] = dp[i-1][j-1] + 1; de lo contrario, dp[i][j] = 0. Lleve un registro del valor máximo observado en todas las celdas.
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 para comparar secuencias
La LCS se usa ampliamente en herramientas de diff (como Unix diff) para comparar archivos. El script de cambios entre dos archivos se deriva de la LCS: las líneas de la LCS no cambian, las líneas adicionales del archivo 1 se eliminan y las líneas adicionales del archivo 2 se insertan. Comprender la LCS le ayuda a valorar cómo los sistemas de control de versiones registran los cambios y por qué se producen conflictos al fusionar.
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)Supersecuencia común más corta
La supersecuencia común más corta (LeetCode 1092) solicita la cadena más corta que contiene s1 y s2 como subsecuencias. Cualquier carácter de la LCS aparece una vez en la supersecuencia; deben incluirse los caracteres que no están en la LCS de ambas cadenas. Longitud = m + n - LCS(s1, s2). Para reconstruirla, use el mismo retroceso de la LCS, pero incluya los caracteres de ambas cadenas en las posiciones donde no coinciden.
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 5Complejidad de la LCS y consejos para entrevistas
El algoritmo clásico de LCS se ejecuta en tiempo O(m×n) y espacio O(m×n), que puede reducirse a O(min(m,n)) mediante la técnica del arreglo rodante. Consejos clave para entrevistas: (1) Defina claramente qué representa el estado de DP antes de programar. (2) Distinga los casos de coincidencia y de no coincidencia. (3) Si le solicitan reconstruir la secuencia, describa el retroceso antes de implementarlo. (4) Mencione la subsecuencia creciente más larga (LIS) como un problema relacionado de una dimensión que puede resolverse en O(n log n) mediante 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)Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que: la LCS usa dp[i][j] = dp[i-1][j-1]+1 cuando hay coincidencia y, de lo contrario, max(dp[i-1][j], dp[i][j-1]), la secuencia real se reconstruye recorriendo en diagonal cuando hay coincidencias y hacia el vecino mayor cuando no las hay, y la LCS es la base de la distancia de edición, las operaciones de eliminación, la supersecuencia común más corta y las herramientas de diff. A continuación, deduciremos la recurrencia de la distancia de edición (Levenshtein), que añade sustituciones al marco de la LCS.
Preguntas frecuentes
¿La lección «Subsecuencia común más larga» es gratis?
Sí — el texto completo de «Subsecuencia común más larga» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Subsecuencia común más larga»?
Defina la recurrencia de LCS para dos strings, rellene la tabla 2D y reconstruya la subsecuencia real retrocediendo por la tabla. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Subsecuencia común más larga»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Rutas únicas y suma mínima de rutas en cuadrículas
- Subsecuencia común más larga
- Distancia de edición (Levenshtein)
- Optimización espacial para DP 2D