Longest Common Subsequence

Q: ¿Cuál es la complejidad temporal de la subsecuencia común más larga?

La solución con tabla se ejecuta en tiempo O(n × m) , donde n y m son las dos longitudes: llena una celda por cada par de prefijos. Necesita 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.

MedioProgramación dinámica

+10

Se te dan dos cadenas, text1 y text2. Una subsecuencia de una cadena conserva algunas de sus letras en su orden original y descarta las demás; las letras conservadas no tienen que estar juntas. Devuelve la longitud de la cadena más larga que sea una subsecuencia de ambas, o 0 si las dos cadenas no tienen ninguna letra en común.

Función

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: la primera cadena
text2string: la segunda cadena
Devuelveinteger: la longitud de la subsecuencia común más larga

Restricciones

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Ambas cadenas contienen solo letras minúsculas del inglés.

Ejemplos

Entrada: text1 = "stone"text2 = "longest"
Salida: 3
Explicación: o, n, e aparecen en este orden en ambas palabras, así que one es una subsecuencia común de longitud 3. En longest, las letras s y t aparecen al final, mientras que en stone aparecen al principio, así que una subsecuencia común que las use solo puede ser st, que es más corta.

Entrada: text1 = "pear"text2 = "reap"
Salida: 2
Explicación: ea aparece en ambas palabras. La p y la r están en lados opuestos de ea en las dos palabras, así que ninguna puede unirse a ella, y la respuesta es 2.

+19 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver una subsecuencia común más larga, no solo su longitud?

Pistas

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

0 de 3 abiertas

Solución

La coincidencia codiciosa de letras no funciona. Una letra puede coincidir en muchos lugares de la otra cadena, y la primera coincidencia puede impedir mejores opciones: emparejar la c de cab con la c del final de abc no deja nada para la a y la b, mientras que omitirla permite encontrar ab. La idea que resuelve el problema es que la respuesta para dos prefijos depende solo de las respuestas para prefijos un poco más cortos. Una tabla de (n+1) × (m+1) números resuelve cada par una sola vez y, como cada fila solo lee la fila anterior, bastan dos filas.

Compara las primeras letras con recursión

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

Intuición

Sea lcs(i, j) la respuesta para los sufijos text1[i:] y text2[j:]. Fíjate en sus primeras letras. Si son iguales, emparéjalas: una subsecuencia común más larga que no use este par puede sustituir su primer par por este sin acortarse. Así que la respuesta es 1 + lcs(i+1, j+1).

Si las letras son diferentes, no se pueden usar ambas, ya que cada una solo podría emparejarse con una letra posterior de la otra cadena, y los pares se cruzarían. Así que se puede descartar una de ellas: la respuesta es max(lcs(i+1, j), lcs(i, j+1)). Cuando alguno de los sufijos está vacío, no tienen nada en común y la respuesta es 0.

Es lento porque cada discrepancia inicia dos llamadas. Si las cadenas no comparten ninguna letra, cada llamada encuentra una discrepancia hasta que se agota una cadena, y el número de llamadas crece como el número de formas de intercalar las dos cadenas. Para dos cadenas de 20 letras, eso equivale a unas 2.8 × 10^11 llamadas; las pruebas grandes tienen 1000 letras cada una. Sin embargo, solo hay (n+1) × (m+1) pares (i, j) diferentes, así que casi todas las llamadas repiten una anterior.

Algoritmo

Escribe lcs(i, j) para los sufijos que empiezan en i y j.
Si i o j supera el final de su cadena, devuelve 0.
Si text1[i] == text2[j], devuelve 1 + lcs(i+1, j+1).
De lo contrario, devuelve max(lcs(i+1, j), lcs(i, j+1)).
La respuesta es lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Completa una tabla de prefijos

Intuición

Estado. Sea dp[i][j] la subsecuencia común más larga de las primeras i letras de text1 y las primeras j letras de text2. Trabajar con prefijos permite que el índice 0 represente una cadena vacía.

Recurrencia. Compara las últimas letras de los dos prefijos, text1[i-1] y text2[j-1]. Si son iguales, emparejalas: dp[i][j] = dp[i-1][j-1] + 1. Si no, descarta una de ellas: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Este es el mismo razonamiento que en la recursión, leído desde el final. Caso base: la fila 0 y la columna 0 son 0, porque un prefijo vacío no tiene nada en común con ningún elemento. Orden: cada celda consulta la celda de arriba, la celda a su izquierda y la que está en diagonal arriba a la izquierda, así que al rellenar fila por fila, de izquierda a derecha, siempre están listas. La respuesta es dp[n][m].

Para pear y reap, la fila de pea es [0, 0, 1, 2, 2]. Su celda correspondiente a rea es 2 porque a coincide con a, así que es el valor de la celda de pe y re, 1, más uno. La última celda, pear frente a reap, compara r con p, que son distintas, y toma el mayor de sus dos vecinos, 2.

La tabla tiene (n+1) × (m+1) celdas y cada una requiere un trabajo constante: alrededor de 10^6 pasos para dos cadenas de 1000 letras. Una versión memoizada de la recursión rellena las mismas celdas, pero recurre hasta una profundidad de n + m llamadas, lo que desborda la pila de llamadas predeterminada en lenguajes como Python.

Algoritmo

Crea una tabla dp de ceros con dimensiones (n+1) × (m+1).
Para i desde 1 hasta n y j desde 1 hasta m, compara text1[i-1] con text2[j-1].
Si coinciden, establece dp[i][j] = dp[i-1][j-1] + 1.
De lo contrario, establece dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Devuelve dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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])
    return dp[n][m]

Conserva solo dos filas

Intuición

La fila i de la tabla solo lee la fila i-1 y sus propias celdas anteriores. Una vez que se termina una fila, nunca se vuelve a leer ninguna fila anterior. Así que conserva dos arreglos, prev para la fila terminada y cur para la fila que se está rellenando, e intercámbialos después de cada fila. La recurrencia y el orden se mantienen exactamente iguales.

Una subsecuencia común de dos cadenas no depende de cuál cadena vaya primero, así que puedes intercambiarlas y hacer que las filas recorran la más corta. Cada fila contiene entonces min(n, m) + 1 números: 1001 en lugar de un millón de celdas para las entradas más grandes, con los mismos 10^6 pasos de trabajo.

La primera entrada de cada fila representa un prefijo vacío de la cadena más corta, así que debe permanecer en 0. La respuesta es la última entrada de la última fila terminada.

Algoritmo

Si text2 es más largo que text1, intercámbialos.
Crea prev y cur, cada uno con m + 1 ceros, donde m es la longitud más corta.
Por cada letra de text1, rellena cur[1..m] con la misma regla que en la tabla, leyendo prev para la fila de arriba.
Intercambia prev y cur.
Devuelve prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Errores comunes y casos límite

La recurrencia es corta, y la mayoría de los errores son desfases de una posición o añaden una coincidencia en el lugar equivocado.

Mezclar los índices de la tabla con los índices de la cadena. La celda dp[i][j] compara text1[i-1] con text2[j-1], porque la fila 0 es el prefijo vacío.
Cuando hay una coincidencia, sumar uno a max(dp[i-1][j], dp[i][j-1]) en lugar de a dp[i-1][j-1]. Esto puede usar una letra dos veces: aa frente a a devolvería 2 en lugar de 1.
Buscar coincidencias de forma voraz con dos punteros. cab frente a abc empareja las dos letras c y devuelve 1, mientras que ab da 2.
Escribir en la fila que todavía se está leyendo. Con dos filas, cada valor de la fila anterior debe obtenerse de prev, y cur[0] debe permanecer en 0.
Resolver por error el problema de la subcadena común más larga. Una subsecuencia puede omitir letras; una subcadena no.
Usar memoización con recursión para cadenas de 1000 letras. La profundidad de las llamadas alcanza 2000, por encima del límite predeterminado de Python, que es 1000.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la subsecuencia común más larga?

La solución con tabla se ejecuta en tiempo O(n × m), donde n y m son las dos longitudes: llena una celda por cada par de prefijos. Necesita 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.

¿Cuál es la diferencia entre la subsecuencia común más larga y la subcadena común más larga?

Una subsecuencia puede omitir letras siempre que se mantenga el orden, mientras que una subcadena es un bloque de letras contiguas. Para stone y longest, la subsecuencia común más larga es one (3), pero la subcadena común más larga es on (2). La versión de subcadena utiliza una tabla similar, pero una discrepancia restablece la celda a 0 en lugar de copiar una celda vecina.

¿Cómo se imprime la subsecuencia común más larga?

Completa toda la tabla y después recorre el camino de vuelta desde dp[n][m]. Cuando las dos letras de la celda actual coincidan, esa letra forma parte de la respuesta: anótala y avanza en diagonal hacia arriba y a la izquierda. De lo contrario, avanza hacia la celda vecina de arriba o de la izquierda que tenga el valor más grande. Invierte el orden de las letras anotadas al final. La versión de dos filas no puede hacerlo, porque ha descartado las filas anteriores.

¿Qué relación tiene LCS con las herramientas diff y la distancia de edición?

Una comparación entre dos versiones de un archivo encuentra la subsecuencia común más larga de sus líneas; cada línea que queda fuera de ella se muestra como añadida o eliminada. Del mismo modo, el menor número de inserciones y eliminaciones que convierte una cadena en la otra es n + m - 2 × LCS. La distancia de edición también permite reemplazar una letra, así que utiliza su propia tabla con una tercera opción por celda.

Python

def longestCommonSubsequence(text1, text2):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

text1 = "stone"
text2 = "longest"

Esperado

Longest Common Subsequence

Función

Restricciones

Ejemplos

Pistas

Solución

Compara las primeras letras con recursión

Completa una tabla de prefijos

Conserva solo dos filas

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares