Longest Common Subsequence

Q: Qual é a complexidade de tempo da subsequência comum mais longa?

A solução com tabela é executada em tempo O(n × m) , uma célula por par de prefixos. Ela precisa de memória O(n × m) para a tabela completa, ou O(min(n, m)) com duas linhas. A recursão simples sem uma tabela é exponencial.

MédioProgramação dinâmica

+10

Você recebe duas strings, text1 e text2. Uma subsequência de uma string mantém algumas de suas letras na ordem original e descarta as demais; as letras mantidas não precisam estar lado a lado. Retorne o comprimento da string mais longa que seja uma subsequência de ambas, ou 0 se as duas strings não tiverem nenhuma letra em comum.

Função

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

text1string: a primeira string
text2string: a segunda string
Retornainteger: o comprimento da maior subsequência comum

Restrições

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Ambas as strings contêm apenas letras minúsculas do alfabeto inglês.

Exemplos

Entrada: text1 = "stone"text2 = "longest"
Saída: 3
Explicação: o, n, e aparecem nessa ordem em ambas as palavras, então one é comum, com comprimento 3. As letras s e t aparecem por último em longest, mas primeiro em stone, então usá-las resulta em no máximo st.

Entrada: text1 = "pear"text2 = "reap"
Saída: 2
Explicação: ea aparece nas duas palavras. O p e o r ficam em lados opostos de ea nas duas palavras, então nenhum deles pode se juntar a ele, e a resposta é 2.

Para ir além

Você pode retornar uma subsequência comum mais longa propriamente dita, junto com seu comprimento?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A correspondência gulosa falha: parear o c de cab com o último c de abc não deixa nada para a e b; ignorá-lo encontra ab. A resposta para dois prefixos depende das respostas para prefixos mais curtos, então uma tabela de (n+1) × (m+1) resolve cada par uma vez. Cada linha lê apenas a linha acima, então duas linhas são suficientes.

Compare as primeiras letras com recursão

Correta, mas não termina nos maiores testes

Intuição

Seja lcs(i, j) a resposta para os sufixos text1[i:] e text2[j:]. Se as primeiras letras forem iguais, combine-as: uma subsequência comum mais longa que ignore esse par pode trocar seu primeiro par por este sem ficar mais curta. Portanto, a resposta é 1 + lcs(i+1, j+1).

Se as letras forem diferentes, elas não podem ser usadas juntas, pois seus pares fariam os pares se cruzarem. Portanto, uma delas pode ser descartada: max(lcs(i+1, j), lcs(i, j+1)). Um sufixo vazio resulta em 0.

Cada divergência inicia duas chamadas. Duas strings de 20 letras sem nenhuma letra em comum já exigem cerca de 2.8 × 10^11 chamadas, mas há apenas (n+1) × (m+1) pares diferentes (i, j), então quase todas as chamadas repetem uma anterior.

Algoritmo

Escreva lcs(i, j) para os sufixos que começam em i e j.
Se i ou j estiver além do fim de sua string, retorne 0.
Se text1[i] == text2[j], retorne 1 + lcs(i+1, j+1).
Caso contrário, retorne max(lcs(i+1, j), lcs(i, j+1)).
A resposta é 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)

Preencha uma tabela de prefixos

Intuição

Seja dp[i][j] a resposta para as primeiras i letras de text1 e as primeiras j letras de text2, então o índice 0 significa um prefixo vazio, e a linha 0 e a coluna 0 são 0. Compare as últimas letras dos dois prefixos, text1[i-1] e text2[j-1]: letras iguais formam um par, dp[i-1][j-1] + 1; letras diferentes descartam uma delas, max(dp[i-1][j], dp[i][j-1]). É a recorrência lida do fim.

Cada célula lê as células acima, à esquerda e na diagonal superior esquerda, então preencher linha por linha, da esquerda para a direita, garante que elas já estejam prontas. Para pear e reap, a linha para pea é [0, 0, 1, 2, 2]; sua célula para rea é 2 porque a corresponde a a, somando um à célula para pe e re.

Duas strings de 1000 letras levam cerca de 10^6 passos de tempo constante.

Algoritmo

Crie uma tabela dp com (n+1) × (m+1) zeros.
Para i de 1 a n e j de 1 a m, compare text1[i-1] com text2[j-1].
Em caso de correspondência, defina dp[i][j] = dp[i-1][j-1] + 1.
Caso contrário, defina dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Retorne 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]

Mantenha apenas duas linhas

Intuição

Quando uma linha termina de ser preenchida, as linhas acima dela nunca mais são lidas. Mantenha prev para a linha concluída e cur para a linha que está sendo preenchida, e troque-as após cada linha. A recorrência e a ordem permanecem as mesmas.

A resposta não depende de qual string vem primeiro, então faça as linhas percorrerem a string mais curta. Cada linha então contém min(n, m) + 1 números: 1001 em vez de um milhão de células para as maiores entradas, com os mesmos 10^6 passos.

Algoritmo

Se text2 for maior que text1, troque-os.
Crie prev e cur, cada um com m + 1 zeros, em que m é o menor comprimento.
Para cada letra de text1, preencha cur[1..m] com a mesma regra da tabela, lendo prev para a linha acima.
Troque prev e cur.
Retorne 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]

Armadilhas e casos extremos

Misturar índices da tabela com índices de strings. A célula dp[i][j] compara text1[i-1] com text2[j-1], porque a linha 0 é o prefixo vazio.
Ao encontrar uma correspondência, somar um a max(dp[i-1][j], dp[i][j-1]) em vez de a dp[i-1][j-1]. Isso pode usar uma letra duas vezes: aa comparado com a retornaria 2 em vez de 1.
Escrever na linha que ainda está sendo lida. Com duas linhas, todos os valores da linha acima devem vir de prev, e cur[0] deve permanecer 0.
Memorizar a recursão em Python com strings de 1000 letras. A profundidade das chamadas chega a 2000, ultrapassando o limite padrão de 1000.

Perguntas frequentes3

Qual é a complexidade de tempo da subsequência comum mais longa?

A solução com tabela é executada em tempo O(n × m), uma célula por par de prefixos. Ela precisa de memória O(n × m) para a tabela completa, ou O(min(n, m)) com duas linhas. A recursão simples sem uma tabela é exponencial.

Qual é a diferença entre subsequência comum mais longa e substring comum mais longa?

Uma subsequência pode pular letras, desde que a ordem seja mantida; uma substring é um bloco de letras vizinhas. Para stone e longest, a maior subsequência comum é one (3), mas a maior substring comum é on (2). A tabela de substrings redefine uma célula para 0 quando há uma incompatibilidade, em vez de copiar uma célula vizinha.

Qual é a relação entre LCS, ferramentas diff e distância de edição?

Um diff entre duas versões de um arquivo mantém a maior subsequência comum de suas linhas e mostra todas as outras linhas como adicionadas ou removidas. O menor número de inserções e remoções necessário para transformar uma string na outra é n + m - 2 × LCS. A distância de edição também permite substituir uma letra, então ela precisa de sua própria tabela.

def longestCommonSubsequence(text1, text2):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

text1 = "stone"
text2 = "longest"

Saída Esperada

Longest Common Subsequence

Função

Restrições

Exemplos

Dicas

Solução

Compare as primeiras letras com recursão

Preencha uma tabela de prefixos

Mantenha apenas duas linhas

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos