Distancia de edición paso a paso
Inserte, elimine o sustituya para transformar
Distancia de edición paso a paso es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 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é mide la distancia de edición
La distancia de edición es el número mínimo de ediciones de un solo carácter necesarias para transformar una cadena en otra. Indica cuánto se diferencian realmente dos palabras.
Las tres operaciones
Puede insertar, eliminar o reemplazar un carácter por cada edición. En el problema estándar, cada operación cuesta exactamente uno.
Defina el estado
Sea dp[i][j] el número de ediciones necesarias para transformar los primeros i caracteres de A en los primeros j caracteres de B.
Coincidencia gratuita
Si los caracteres actuales ya coinciden, no se necesita ninguna edición. Simplemente conserve el valor diagonal.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]De lo contrario, pague uno
Cuando los caracteres son diferentes, tome el vecino más barato y sume una edición. Ese mínimo más uno cubre las tres operaciones.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Qué representa cada vecino
La celda de arriba representa una eliminación, la celda de la izquierda una inserción y la diagonal un reemplazo. El mínimo simplemente elige la opción más barata.
Casos base de la cadena vacía
Transformar una cadena de longitud i en una vacía requiere i eliminaciones. Por tanto, rellene la fila y la columna primeras con 0, 1, 2 y así sucesivamente.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jDimensione la tabla
Utilice una cuadrícula de n+1 por m+1 para que los prefijos vacíos tengan su propia fila y columna. Este relleno mantiene sencillos los bucles.
dp = [[0] * (m+1) for _ in range(n+1)]Rellene en orden
Recorra i y j en orden ascendente desde 1. Cada celda solo depende de vecinos de arriba, de la izquierda y de la diagonal que ya están rellenados.
for i in range(1, n+1):
for j in range(1, m+1):
...Lea la distancia
El número mínimo de ediciones termina en la esquina. Su respuesta es dp[n][m] cuando la tabla está completa.
distance = dp[n][m]Costos y variantes
Esto se ejecuta en tiempo O(n por m). En tareas reales pueden asignarse costos diferentes a cada operación, pero la misma recurrencia sigue funcionando.
Comprobación rápida
Los caracteres A[i-1] y B[j-1] son diferentes. ¿Qué recurrencia proporciona la distancia de edición?
Repaso: distancia de edición
Una coincidencia significa conservar la diagonal; una diferencia significa sumar 1 al mínimo de los tres vecinos. Inicialice los bordes y lea dp[n][m]. ✏️
Preguntas frecuentes
¿La lección «Distancia de edición paso a paso» es gratis?
Sí — el texto completo de «Distancia de edición paso a paso» 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 «Distancia de edición paso a paso»?
Inserte, elimine o sustituya para transformar 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 4 de 4.
¿Cuánto tiempo toma la lección «Distancia de edición paso a paso»?
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
- Conteo de caminos en una cuadrícula
- Suma mínima de caminos con obstáculos
- Subsecuencia común más larga
- Distancia de edición paso a paso