Distancia de edición (Levenshtein)
Derive la recurrencia de la distancia de edición para operaciones de inserción, eliminación y sustitución, y rellene la tabla de DP para pares de strings de distintas longitudes.
Distancia de edición (Levenshtein) es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 3 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
El problema de la distancia de edición
La distancia de edición (distancia de Levenshtein, LeetCode 72) plantea la siguiente pregunta: ¿cuál es el número mínimo de operaciones de inserción, eliminación o reemplazo necesarias para transformar una cadena en otra? Por ejemplo, para transformar 'horse' en 'ros': reemplace 'h'→'r' (horse→rorse), elimine 'r' (rorse→rose) y elimine 'e' (rose→ros): 3 operaciones. La distancia de edición es fundamental en los correctores ortográficos, la alineación de ADN y la coincidencia aproximada.
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')Estado y recurrencia de DP
Defina dp[i][j] como la distancia de edición mínima entre word1[:i] y word2[:j]. Si word1[i-1] == word2[j-1], no se necesita ninguna operación: dp[i][j] = dp[i-1][j-1]. De lo contrario, tome el mínimo de tres operaciones: insertar dp[i][j-1] + 1, eliminar dp[i-1][j] + 1, reemplazar dp[i-1][j-1] + 1. Casos base: dp[i][0] = i (eliminar todo word1) y dp[0][j] = j (insertar todo word2).
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
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] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5Comprensión de las tres operaciones
Las tres operaciones se corresponden directamente con movimientos en la tabla de DP: Reemplazar dp[i-1][j-1]+1: hicimos coincidir ambos caracteres, pero pagamos un costo. Eliminar de word1 dp[i-1][j]+1: quite un carácter de word1 (muévase hacia arriba en la tabla). Insertar en word1 dp[i][j-1]+1: inserte un carácter para que coincida con word2 (muévase hacia la izquierda). El mínimo de las tres opciones proporciona la ruta de edición óptima.
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
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]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)Optimización del espacio a O(n)
La distancia de edición solo necesita la fila actual y la anterior. Use un arreglo unidimensional de tamaño n+1 y siga por separado el valor diagonal (dp[i-1][j-1]) antes de actualizar cada celda. Procese de izquierda a derecha: temp = dp[j] (valor anterior = dp[i-1][j]); actualice dp[j] usando dp[j] (eliminación), dp[j-1] (inserción) y diagonal (reemplazo).
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5Reconstrucción de las operaciones de edición
Para reconstruir la secuencia real de ediciones, recorra hacia atrás la tabla de DP desde (m, n). En cada celda: si word1[i-1] == word2[j-1], muévase en diagonal (no hay ninguna operación). De lo contrario, determine cuál de los tres vecinos produjo el mínimo y registre la operación correspondiente. Esto produce el script de edición en orden inverso; inviértalo para obtener la respuesta final.
def edit_ops(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
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]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)Comprobación de una distancia de una edición
Un problema de entrevista más sencillo: ¿difieren dos cadenas en exactamente una edición? Puede resolverse en O(n) sin DP. Recorra ambas cadenas simultáneamente. Cuando encuentre una discrepancia, pruebe las tres operaciones (saltar un carácter en s1, saltar uno en s2 o saltar ambos) y compruebe si los segmentos restantes son idénticos. Si se producen dos discrepancias, devuelva False. Este enfoque voraz evita la DP completa O(mn) cuando solo necesita saber si la distancia ≤ 1.
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # FalseComparación entre la distancia de edición y la LCS
La distancia de edición (con las tres operaciones) y la LCS ofrecen perspectivas complementarias sobre la similitud entre cadenas. La distancia de edición cuenta la diferencia; la LCS cuenta la similitud. Cuando solo se permiten inserciones y eliminaciones (sin reemplazos), la distancia de edición = m + n - 2×LCS. Cuando se permiten sustituciones, la DP es ligeramente diferente: la diagonal aporta dp[i-1][j-1] si hay coincidencia (sin costo) o dp[i-1][j-1]+1 si hay reemplazo. Ambos algoritmos se ejecutan en tiempo O(mn).
def lcs_len(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 edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)Coincidencia aproximada de cadenas
La distancia de edición permite la coincidencia aproximada en aplicaciones reales. Un corrector ortográfico sugiere correcciones que se encuentran a una distancia de edición de 1 o 2 de la palabra escrita. El desafío a gran escala consiste en evitar O(mn × dict_size) comparaciones. Entre las soluciones se incluyen los BK-trees (un árbol métrico para la distancia de edición), la indexación de n-gramas y algoritmos de coincidencia aproximada de cadenas como Bitap. Comprender la DP subyacente le ayuda a razonar sobre la eficiencia de estas herramientas de nivel superior.
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morseDistancia de edición ponderada
En algunas aplicaciones, las distintas operaciones tienen costos diferentes. Por ejemplo, transponer caracteres adyacentes (un error tipográfico común) podría costar menos que un reemplazo completo. La distancia de Damerau-Levenshtein añade la transposición como cuarta operación. La DP se amplía para comprobar también dp[i-2][j-2]+1 cuando word1[i-1]==word2[j-2] y word1[i-2]==word2[j-1]. Esto modela con mayor precisión los errores tipográficos al escribir en el teclado.
def damerau_levenshtein(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)Alineación de secuencias de ADN
La bioinformática utiliza variantes de la distancia de edición para la alineación de secuencias de ADN. El algoritmo de Needleman-Wunsch es una DP de alineación global estrechamente relacionada con la LCS y la distancia de edición, en la que una coincidencia proporciona +1, una discrepancia proporciona -1 y un hueco (inserción/eliminación) aplica una penalización. La variante Smith-Waterman realiza una alineación local (encuentra la subcadena con la mejor coincidencia). Ambos son algoritmos de DP O(mn) con la misma estructura de llenado de la tabla.
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment scoreEnfoque para entrevistas sobre la distancia de edición
Cuando le pregunten por la distancia de edición en una entrevista: (1) Confirme las operaciones permitidas (inserción/eliminación/reemplazo). (2) Defina claramente el estado de DP. (3) Escriba explícitamente los tres casos y la recurrencia. (4) Indique los casos base: dp[i][0]=i y dp[0][j]=j. (5) Mencione la optimización del espacio a O(n). (6) Si tiene tiempo, recorra un ejemplo pequeño como 'cat'→'cut' (un reemplazo) para validar el resultado. Los límites de complejidad estándar son O(mn) en tiempo y una reducción del espacio de O(mn) a O(n).
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3Comprobació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 distancia de edición dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost), con cost=0 cuando hay coincidencia y, en caso contrario, 1, los casos base dp[i][0]=i y dp[0][j]=j representan la transformación desde o hacia una cadena vacía, y la optimización del espacio a O(n) usa un arreglo unidimensional rodante con una variable diagonal. A continuación, aplicaremos la misma técnica del arreglo rodante para reducir las tablas de DP bidimensionales de un espacio O(mn) a O(min(m,n)).
Preguntas frecuentes
¿La lección «Distancia de edición (Levenshtein)» es gratis?
Sí — el texto completo de «Distancia de edición (Levenshtein)» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Distancia de edición (Levenshtein)»?
Derive la recurrencia de la distancia de edición para operaciones de inserción, eliminación y sustitución, y rellene la tabla de DP para pares de strings de distintas longitudes. Practicas DSA 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 DSA Interview Prep?
No se requiere experiencia previa. DSA 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 3 de 4.
¿Cuánto tiempo toma la lección «Distancia de edición (Levenshtein)»?
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 DSA Interview Prep?
Sí. Cada lección de DSA 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