Edit Distance

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

Sí. Completa 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 valor de la fila actual. Solo se pierde el valor diagonal, así que guarda el valor anterior de row[j] en una variable 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 tres maneras: insertar una letra en cualquier lugar, eliminar una letra o reemplazar una letra por otra distinta. Devuelve el número mínimo de ediciones necesarias para transformar word1 en word2.

Función

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

word1string: la palabra que editas
word2string: la palabra «alcanzar»
Devuelveinteger: la menor cantidad de inserciones, eliminaciones y sustituciones que convierten 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 t y la t por p: spot se convierte en stot, después en 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 t al final para obtener ardent. Reemplazar 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, después inserta e. Dos ediciones no bastan: r y a no están en shine, así que cada una necesita una edición que mantenga la longitud, y la palabra aún debe crecer en uno.

Para ir más allá

¿También puedes devolver una lista de ediciones más corta, además de su cantidad?

Pistas

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

0 de 3 abiertas

Solución

Las ediciones interactúan: garden y ardent difieren en las seis posiciones, pero bastan dos ediciones. Así que fíjate en la última letra de cada palabra. O bien las dos coinciden, o una de tres ediciones hace que coincidan, y cada opción deja el mismo problema en prefijos más cortos. Una tabla resuelve una sola vez cada par de prefijos.

Prueba las tres ediciones con recursión

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

Intuición

Sea edits(i, j) la menor cantidad de ediciones que convierte el sufijo word1[i:] en word2[j:]. Si las primeras letras coinciden, consérvalas y avanza ambos índices: gastar una edición en una letra coincidente nunca ayuda. De lo contrario, toma 1 más el menor costo de tres llamadas: una sustitución avanza ambos índices, una eliminación de word1[i] avanza i, y una inserción de word2[j] avanza j. Cuando se agota una palabra, cada letra que queda en la otra cuesta una edición.

Cada discrepancia inicia tres llamadas: dos palabras de 15 letras sin ninguna letra en común requieren alrededor de 6.7 × 10^10 llamadas. Sin embargo, solo hay (n+1) × (m+1) pares distintos (i, j), así que casi todas las llamadas repiten una anterior.

Algoritmo

Si i ha superado el final de word1, devuelve m - j; si j ha superado el final de word2, devuelve n - i.
Si word1[i] == word2[j], devuelve edits(i+1, j+1).
En caso contrario, devuelve 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)).
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

Sea dp[i][j] el mínimo número de ediciones necesarias para convertir las primeras i letras de word1 en las primeras j letras de word2. Si word1[i-1] es igual a word2[j-1], copia el valor diagonal dp[i-1][j-1]. De lo contrario, suma 1 al vecino más barato: la diagonal corresponde a una sustitución, la celda de arriba a eliminar word1[i-1] y la celda de la izquierda a insertar word2[j-1]. La fila y la columna iniciales no son ceros: convertir i letras en nada requiere i eliminaciones, así que dp[i][0] = i, y de igual forma dp[0][j] = j.

Para convertir spot en stop, la última fila es [4, 3, 2, 2, 2]. La celda final compara t con p; su valor diagonal (convertir spo en sto) es 1 y sus otros vecinos son 2, así que la respuesta es 1 + 1 = 2. Dos palabras de 500 letras llenan 2.5 × 10^5 celdas, cada una en tiempo constante.

Algoritmo

Crea dp con (n+1) × (m+1) celdas, dp[i][0] = i y dp[0][j] = j.
Para i de 1 a n y j de 1 a m: si word1[i-1] == word2[j-1], establece dp[i][j] = dp[i-1][j-1].
De lo contrario, establece 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]

Conserva solo dos filas

Intuición

La fila i solo lee la fila i-1 y sus propias celdas a la izquierda, así que bastan dos arreglos: prev para la fila terminada y cur para la fila que estás rellenando. La diagonal es prev[j-1], la de arriba es prev[j] y la de la izquierda es cur[j-1]. La columna base ahora está en la primera entrada de cada fila, así que establece cur[0] = i antes de rellenar la fila i.

Convertir word2 en word1 requiere el mismo número de ediciones, ya que las inserciones y las eliminaciones se intercambian. Intercambia las palabras para que las filas recorran la más corta: min(n, m) + 1 números por fila en lugar de una tabla de hasta 251,001 celdas, con el mismo trabajo O(n × m).

Algoritmo

Si word2 es más largo que word1, intercámbialos.
Establece prev = [0, 1, ..., m].
Para cada i desde 1 hasta n, establece cur[0] = i y rellena cur[1..m] con la regla de la tabla, leyendo la diagonal y la fila superior de prev y la celda de la izquierda de cur. Después, 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

Llenar 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.
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 desfasadas.
Aplicar un costo de edición cuando hay una coincidencia. Con 1 + min(...) para letras iguales, convertir a en a cuesta 1.
Leer el vecino de la izquierda de prev en lugar de cur. La izquierda es la inserción de word2[j-1] en la fila actual.
Recursión con memorización en Python para palabras de 500 letras. Las llamadas llegan hasta una profundidad de 1000, por encima del límite de recursión predeterminado.

Preguntas frecuentes3

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

La solución con tabla llena una celda por cada par de prefijos en tiempo constante: tiempo O(n × m) para longitudes n y m. Usa memoria O(n × m) 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?

Esta versión es la distancia de Levenshtein: insertar, borrar y reemplazar cuestan una unidad cada uno. Distancia de edición es el nombre de la familia. Solo inserciones y eliminaciones da n + m - 2 × LCS; solo reemplazos en cadenas de igual longitud da la distancia de Hamming, y añadir un intercambio de dos letras vecinas da la versión de Damerau.

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

Sí. Completa 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 valor de la fila actual. Solo se pierde el valor diagonal, así que guarda el valor anterior de row[j] en una variable y úsalo como diagonal para j + 1.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

word1 = "spot"
word2 = "stop"

Salida Esperada

Edit Distance

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba las tres ediciones con recursión

Completa una tabla de prefijos

Conserva solo dos filas

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares