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) , 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 el resto; las letras conservadas no tienen que ser consecutivas. 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 común, longitud 3. Las letras s y t aparecen al final de longest, pero al principio de stone, así que usarlas da como máximo st.

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.

Para ir más allá

¿Puedes devolver una de las subsecuencias comunes más largas, junto con su longitud?

Pistas

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

0 de 3 abiertas

Solución

La coincidencia codiciosa falla: emparejar la c de cab con la última c de abc no deja nada para a y b; si se omite, se encuentra ab. La respuesta para dos prefijos depende de las respuestas para prefijos más cortos, así que una tabla de (n+1) × (m+1) resuelve cada par una sola vez. Cada fila solo lee la fila de arriba, así que 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:]. Si sus primeras letras son iguales, emparejémoslas: una subsecuencia común más larga que omita este par puede cambiar 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, porque sus parejas harían que los pares se cruzaran. Así que se puede descartar una de ellas: max(lcs(i+1, j), lcs(i, j+1)). Un sufijo vacío da 0.

Cada discrepancia inicia dos llamadas. Dos cadenas de 20 letras sin ninguna letra en común ya requieren unas 2.8 × 10^11 llamadas, pero solo hay (n+1) × (m+1) pares diferentes (i, j), 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 está después del 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)

Rellena una tabla de prefijos

Intuición

Sea dp[i][j] la respuesta para las primeras i letras de text1 y las primeras j letras de text2, de modo que el índice 0 representa un prefijo vacío y la fila 0 y la columna 0 son 0. Compara las últimas letras de los dos prefijos, text1[i-1] y text2[j-1]: si son iguales, se emparejan, dp[i-1][j-1] + 1; si son diferentes, se descarta una de ellas, max(dp[i-1][j], dp[i][j-1]). Es la recursión leída desde el final.

Cada celda consulta las celdas de arriba, de la izquierda y en diagonal arriba a la izquierda, así que al rellenar fila por fila, de izquierda a derecha, siempre las encuentra listas. Para pear y reap, la fila para pea es [0, 0, 1, 2, 2]; su celda para rea es 2 porque la a coincide con la a, sumando uno a la celda para pe y re.

Dos cadenas de 1000 letras requieren unos 10^6 pasos de tiempo constante.

Algoritmo

Crea una tabla dp de (n+1) × (m+1) ceros.
Para i de 1 a n y j de 1 a m, compara text1[i-1] con text2[j-1].
Si coinciden, asigna dp[i][j] = dp[i-1][j-1] + 1.
De lo contrario, asigna 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

Una vez que se termina una fila, nunca se vuelven a leer las filas que están por encima. Mantén prev para la fila terminada y cur para la fila que se está rellenando, e intercámbialas después de cada fila. La recurrencia y el orden se mantienen iguales.

La respuesta no depende de cuál cadena aparece primero, así que haz 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.

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, llena cur[1..m] siguiendo la misma regla que en la tabla y 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

Mezclar índices de la tabla con índices de cadenas. La celda dp[i][j] compara text1[i-1] con text2[j-1], porque la fila 0 es el prefijo vacío.
En caso de coincidencia, sumar uno a max(dp[i-1][j], dp[i][j-1]) en lugar de a dp[i-1][j-1]. Eso puede usar una letra dos veces: aa frente a a devolvería 2 en lugar de 1.
Escribir en la fila que todavía estás leyendo. Con dos filas, todos los valores de la fila anterior deben provenir de prev, y cur[0] debe seguir siendo 0.
Almacenar en caché la recursión en Python con cadenas de 1000 letras. La profundidad de las llamadas llega a 2000, por encima del límite predeterminado de 1000.

Preguntas frecuentes3

¿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), 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 saltarse letras siempre que se mantenga el orden; 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 tabla de subcadenas restablece una celda a 0 cuando hay una discrepancia, en lugar de copiar la celda vecina.

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

Una diferencia entre dos versiones de un archivo conserva la subsecuencia común más larga de sus líneas y muestra todas las demás líneas como añadidas o eliminadas. El menor número de inserciones y eliminaciones necesarias para transformar una cadena en la otra es n + m - 2 × LCS. La distancia de edición también permite reemplazar una letra, así que necesita su propia tabla.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

text1 = "stone"
text2 = "longest"

Salida Esperada

Longest Common Subsequence

Función

Restricciones

Ejemplos

Pistas

Solución

Compara las primeras letras con recursión

Rellena una tabla de prefijos

Conserva solo dos filas

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares