Edit Distance

Q: ¿Cuál es la complejidad temporal de la distancia de edición?

La solución con tabla se ejecuta en tiempo O(n × m) , donde n y m son las dos longitudes, porque rellena una celda por cada par de prefijos con trabajo constante. Usa O(n × m) de memoria para la tabla completa, o O(min(n, m)) con dos filas. La recursión simple sin una tabla es exponencial.

Q: ¿Cómo obtienes la lista de ediciones, no solo el recuento?

Conserva la tabla completa y retrocede desde dp[n][m] . Si las letras coinciden, avanza en diagonal sin hacer ninguna edición. De lo contrario, avanza hacia el vecino cuyo valor es uno menos: la diagonal es una sustitución, hacia arriba es una eliminación y hacia la izquierda es una inserción. Detente en dp[0][0] y lee las ediciones en orden inverso. La versión de dos filas no puede hacerlo por sí sola, porque ha descartado las filas anteriores.

Q: ¿Se puede resolver la distancia de edición con un solo array?

Sí. Rellena una matriz row en el mismo lugar, de izquierda a derecha. Antes de sobrescribir row[j] , todavía contiene el valor de la fila anterior, y row[j-1] ya contiene el de la fila actual. El único valor que pierdes es el diagonal, así que guárdalo en una variable: guarda el valor anterior de row[j] antes de escribir y úsalo como diagonal para j + 1 .

DifícilProgramación dinámica

+10

Se te dan dos palabras, word1 y word2. Una edición cambia word1 de una de estas tres maneras: insertar una letra en cualquier lugar, eliminar una letra o reemplazar una letra por otra diferente. Devuelve el menor número de ediciones que transforma word1 en word2.

Función

minDistance(word1: string, word2: string) → integer

word1string: la palabra que editas
word2string: la palabra que hay que alcanzar
Devuelveinteger: la menor cantidad de inserciones, eliminaciones y sustituciones necesarias para convertir word1 en word2

Restricciones

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Ambas palabras contienen únicamente letras minúsculas del inglés.

Ejemplos

Entrada: word1 = "spot"word2 = "stop"
Salida: 2
Explicación: Reemplaza la p por una t y la t por una p: spot se convierte en stot, después stop. Una edición no es suficiente, porque las palabras difieren en dos lugares y una inserción o una eliminación cambiaría la longitud.

Entrada: word1 = "garden"word2 = "ardent"
Salida: 2
Explicación: Elimina la g para obtener arden, después inserta una t al final para obtener ardent. Sustituir letra por letra costaría 6, porque las dos palabras difieren en cada posición.

Entrada: word1 = "rain"word2 = "shine"
Salida: 3
Explicación: Reemplaza r por s y a por h para obtener shin; después inserta e. No se puede hacer con dos ediciones: r y a no aparecen en shine, así que cada una requiere una edición que no alarga la palabra, y la palabra aún tiene que crecer una letra.

+21 pruebas ocultas al enviar

Para ir más allá

¿También puedes devolver una lista de ediciones más corta, no solo decir cuántas hay?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Las ediciones interactúan, así que no puedes corregir las letras posición por posición: garden y ardent difieren en las seis posiciones, pero bastan dos ediciones una vez que se elimina la g y todo se desplaza a la izquierda. La idea clave es fijarse solo en la última letra de cada palabra. O bien las dos letras ya coinciden, o bien una de exactamente tres ediciones hace que coincidan, y cada opción deja el mismo problema en prefijos más cortos. Una tabla de respuestas de (n+1) × (m+1) resuelve una sola vez cada par de prefijos, y bastan dos filas de esa tabla.

Prueba las tres modificaciones con recursión

Correcto, pero no termina con las pruebas más grandes

Intuición

Sea edits(i, j) la menor cantidad de ediciones necesarias para transformar el sufijo word1[i:] en el sufijo word2[j:]. Fíjate en las primeras letras de los dos sufijos. Si son iguales, consérvalas y avanza ambos índices: una letra coincidente nunca necesita una edición, y cualquier plan que gaste una edición en ella puede modificarse para conservarla sin alargarse.

Si son diferentes, alguna edición debe ocuparse de word1[i] o producir word2[j], y hay exactamente tres maneras. Reemplaza word1[i] por word2[j] y avanza ambos índices: edits(i+1, j+1). Elimina word1[i] y avanza solo i: edits(i+1, j). Inserta word2[j] delante y avanza solo j: edits(i, j+1). La respuesta es 1 más el mínimo de las tres opciones. Cuando se acabe word1, inserta el resto de word2, lo que cuesta m - j; cuando se acabe word2, elimina el resto de word1, lo que cuesta n - i.

Es lento porque cada discrepancia inicia tres llamadas. Para dos palabras de 15 letras sin ninguna letra en común, eso supone unas 6.7 × 10^10 llamadas, y las pruebas grandes tienen 500 letras cada una. Sin embargo, solo hay (n+1) × (m+1) pares distintos (i, j), así que casi todas las llamadas repiten una anterior.

Algoritmo

Escribe edits(i, j) para los sufijos que comienzan en i y j.
Si i está más allá del final de word1, devuelve m - j; si j está más allá del final de word2, devuelve n - i.
Si word1[i] == word2[j], devuelve edits(i+1, j+1).
De lo contrario, devuelve 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) para reemplazar, eliminar e insertar.
La respuesta es edits(0, 0).

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Completa una tabla de prefijos

Intuición

Estado. Sea dp[i][j] el menor número de ediciones que convierte las primeras i letras de word1 en las primeras j letras de word2. El índice 0 representa un prefijo vacío.

Transiciones. Compara las últimas letras de los dos prefijos, word1[i-1] y word2[j-1]. Si son iguales, consérvalas: dp[i][j] = dp[i-1][j-1], la celda en diagonal arriba y a la izquierda. Si no, paga una edición y elige la opción más barata entre tres celdas vecinas. La diagonal dp[i-1][j-1] significa reemplazar word1[i-1] por word2[j-1]. La celda de arriba, dp[i-1][j], significa eliminar word1[i-1]. La celda de la izquierda, dp[i][j-1], significa insertar word2[j-1] al final.

Fila y columna base. A diferencia de muchos problemas con tablas, no son ceros. Convertir i letras en un prefijo vacío requiere i eliminaciones, así que dp[i][0] = i. Construir j letras desde cero requiere j inserciones, así que dp[0][j] = j. Cada celda lee la celda de arriba, la de la izquierda y la diagonal, así que al rellenar fila por fila, de izquierda a derecha, estas ya están listas. La respuesta es dp[n][m].

Aquí está la tabla para convertir spot en stop, con columnas para los prefijos "", s, st, sto, stop. La fila "" es [0, 1, 2, 3, 4], la fila s es [1, 0, 1, 2, 3], la fila sp es [2, 1, 1, 2, 2], la fila spo es [3, 2, 2, 1, 2] y la fila spot es [4, 3, 2, 2, 2]. Lee algunas celdas. s frente a s coincide, así que copia la diagonal 0. sp frente a st no coincide: sus celdas vecinas son 0 en la diagonal, 1 arriba y 1 a la izquierda, así que el resultado es 1 + 0 = 1, un reemplazo. spo frente a sto coincide en la o y copia ese 1. La última celda, spot frente a stop, compara t con p: sus celdas vecinas son 1, 2 y 2, así que la respuesta es 1 + 1 = 2.

La tabla tiene (n+1) × (m+1) celdas, con un trabajo constante en cada una, aproximadamente 2.5 × 10^5 pasos para dos palabras de 500 letras. Una recursión con memorización rellena las mismas celdas, pero puede tener hasta n + m llamadas de profundidad, lo que supera el límite predeterminado de Python de 1000.

Algoritmo

Crea una tabla dp de (n+1) × (m+1) celdas.
Asigna dp[i][0] = i para cada i y dp[0][j] = j para cada j.
Para i de 1 a n y j de 1 a m, si word1[i-1] == word2[j-1], asigna dp[i][j] = dp[i-1][j-1].
De lo contrario, asigna dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Devuelve dp[n][m].

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Mantén solo dos filas

Intuición

La fila i solo lee la fila i-1 y sus propias celdas de la izquierda. Una vez terminada una fila, ya no se vuelven a leer las filas anteriores. Mantén dos arreglos: prev para la fila terminada y cur para la fila que estás completando, e intercámbialos después de cada fila. Las transiciones no cambian: la diagonal es prev[j-1], la de arriba es prev[j] y la de la izquierda es cur[j-1].

La columna base no desaparece. Ahora está en la primera entrada de cada fila, así que asigna cur[0] = i antes de completar la fila i. La fila 0 empieza como [0, 1, 2, ..., m], la fila base.

Convertir word2 en word1 requiere el mismo número de ediciones, porque cada inserción se convierte en una eliminación y cada eliminación, en una inserción. Así que puedes intercambiar las palabras y hacer que las filas recorran la más corta. Cada fila contiene entonces min(n, m) + 1 números en lugar de una tabla de hasta 251,001 celdas, y el trabajo sigue siendo O(n × m).

Algoritmo

Si word2 es más largo que word1, intercámbialos.
Establece prev = [0, 1, ..., m], donde m es la longitud más corta.
Para cada i desde 1 hasta n, establece cur[0] = i y luego completa cur[1..m] con la misma regla, leyendo la diagonal y la fila superior de prev y la izquierda de cur.
Intercambia prev y cur.
Devuelve prev[m].

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Errores comunes y casos límite

La recurrencia es breve, así que la mayoría de los errores están en los casos base o en qué vecino se lee.

Rellenar la fila 0 y la columna 0 con ceros, como en la subsecuencia común más larga. Convertir abc en un prefijo vacío cuesta 3 eliminaciones, no 0, así que dp[i][0] debe ser i y dp[0][j] debe ser j.
Olvidar cur[0] = i en la versión de dos filas. La primera entrada conserva un valor de dos filas atrás, y todas las celdas posteriores quedan mal.
Contabilizar una edición cuando hay una coincidencia. dp[i][j] = 1 + min(...) para letras iguales hace que convertir a en a cueste 1. Si coinciden, copia la diagonal.
Leer el vecino de la izquierda de prev en vez de cur. La izquierda es la fila actual: corresponde a insertar word2[j-1] después de que word1[:i] ya se haya convertido en word2[:j-1].
Comparar posición por posición. Contar los lugares donde las palabras difieren ignora las inserciones y eliminaciones: da 6 para garden y ardent, mientras que la respuesta es 2.
Usar memoización con recursión en palabras de 500 letras. La profundidad de las llamadas llega a 1000, que es el límite predeterminado de Python.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la distancia de edición?

La solución con tabla se ejecuta en tiempo O(n × m), donde n y m son las dos longitudes, porque rellena una celda por cada par de prefijos con trabajo constante. Usa O(n × m) de memoria para la tabla completa, o O(min(n, m)) con dos filas. La recursión simple sin una tabla es exponencial.

¿La distancia de edición es lo mismo que la distancia de Levenshtein?

Sí, esta versión es la distancia de Levenshtein: insertar, eliminar y reemplazar cuestan una unidad cada operación. La distancia de edición es el nombre de la familia. Otras variantes permiten menos o más ediciones: solo insertar y eliminar da n + m - 2 × LCS; solo reemplazar con longitudes iguales da la distancia de Hamming, y añadir el intercambio de dos letras vecinas da la versión de Damerau.

¿Cómo obtienes la lista de ediciones, no solo el recuento?

Conserva la tabla completa y retrocede desde dp[n][m]. Si las letras coinciden, avanza en diagonal sin hacer ninguna edición. De lo contrario, avanza hacia el vecino cuyo valor es uno menos: la diagonal es una sustitución, hacia arriba es una eliminación y hacia la izquierda es una inserción. Detente en dp[0][0] y lee las ediciones en orden inverso. La versión de dos filas no puede hacerlo por sí sola, porque ha descartado las filas anteriores.

¿Se puede resolver la distancia de edición con un solo array?

Sí. Rellena una matriz row en el mismo lugar, de izquierda a derecha. Antes de sobrescribir row[j], todavía contiene el valor de la fila anterior, y row[j-1] ya contiene el de la fila actual. El único valor que pierdes es el diagonal, así que guárdalo en una variable: guarda el valor anterior de row[j] antes de escribir y úsalo como diagonal para j + 1.

Python

def minDistance(word1, word2):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

word1 = "spot"
word2 = "stop"

Esperado

Edit Distance

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba las tres modificaciones con recursión

Completa una tabla de prefijos

Mantén solo dos filas

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares