Longest Common Subsequence

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

A solução com tabela é executada em tempo O(n × m) , em que n e m são os dois comprimentos: ela preenche uma célula para cada par de prefixos. Ela precisa de O(n × m) de memória para a tabela completa, ou O(min(n, m)) usando duas linhas. A recursão simples sem uma tabela tem complexidade exponencial.

Q: Como imprimir a própria subsequência comum mais longa?

Preencha a tabela inteira e, em seguida, volte a partir de dp[n][m] . Quando as duas letras na célula atual forem iguais, essa letra fará parte da resposta: registre-a e avance na diagonal para cima e para a esquerda. Caso contrário, avance para a célula vizinha acima ou à esquerda que contenha o maior valor. Inverta as letras registradas no final. A versão com duas linhas não consegue fazer isso, pois descartou as linhas anteriores.

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 maior string que é 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 é uma subsequência comum de comprimento 3. Em longest, as letras s e t vêm por último, enquanto em stone elas vêm primeiro, então uma subsequência comum que as usa só pode ser st, que é mais curta.

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.

+19 testes ocultos ao enviar

Para ir além

Você pode retornar uma das maiores subsequências comuns, e não apenas seu comprimento?

Dicas

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

0 de 3 abertas

Solução

Não funciona fazer correspondências gananciosas entre letras. Uma letra pode corresponder a vários lugares na outra string, e a primeira correspondência pode impedir outras melhores: emparelhar o c de cab com o c no final de abc não deixa nada para a e b, enquanto ignorá-lo encontra ab. A ideia que resolve isso é que a resposta para dois prefixos depende apenas das respostas para prefixos um pouco menores. Uma tabela de (n+1) × (m+1) números resolve cada par uma vez e, como cada linha lê apenas a linha acima, 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:]. Observe as primeiras letras. Se forem iguais, faça o pareamento: uma subsequência comum mais longa que não use esse par pode trocar seu primeiro par por este sem ficar menor. Portanto, a resposta é 1 + lcs(i+1, j+1).

Se as letras forem diferentes, elas não podem ser usadas ao mesmo tempo, pois cada uma só poderia ser pareada com uma letra posterior da outra string, e os pares se cruzariam. Portanto, uma delas pode ser descartada: a resposta é max(lcs(i+1, j), lcs(i, j+1)). Quando um dos sufixos estiver vazio, nada é comum e a resposta é 0.

O algoritmo é lento porque cada divergência inicia duas chamadas. Se as strings não tiverem nenhuma letra em comum, cada chamada terá uma divergência até uma das strings acabar, e o número de chamadas crescerá como o número de maneiras de intercalar as duas strings. Para duas strings com 20 letras, isso dá cerca de 2.8 × 10^11 chamadas; os testes grandes têm 1000 letras cada. No entanto, há apenas (n+1) × (m+1) pares (i, j) diferentes, 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

Estado. Seja dp[i][j] a subsequência comum mais longa das primeiras i letras de text1 e das primeiras j letras de text2. Trabalhar com prefixos permite que o índice 0 represente uma string vazia.

Recorrência. Compare as últimas letras dos dois prefixos, text1[i-1] e text2[j-1]. Se forem iguais, emparelhe-as: dp[i][j] = dp[i-1][j-1] + 1. Se não, descarte uma delas: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Esse é o mesmo raciocínio da recursão, lido de trás para frente. Caso base: a linha 0 e a coluna 0 são 0, porque um prefixo vazio não tem nada em comum com nenhum outro. Ordem: cada célula consulta a célula acima, a célula à sua esquerda e a que está na diagonal acima e à esquerda; portanto, preencher linha por linha, da esquerda para a direita, garante que elas já estejam prontas. A resposta é dp[n][m].

Para pear e reap, a linha de pea é [0, 0, 1, 2, 2]. A célula correspondente a rea é 2 porque o a corresponde ao a; portanto, ela é igual à célula de pe e re, que vale 1, mais um. A última célula, pear contra reap, compara r com p, que são diferentes, e escolhe o maior valor entre suas duas células vizinhas: 2.

A tabela tem (n+1) × (m+1) células, e cada uma exige um trabalho constante: cerca de 10^6 passos para duas strings de 1000 letras. Uma versão memorizada da recursão preenche as mesmas células, mas faz chamadas recursivas até n + m níveis de profundidade, o que excede o limite padrão da pilha de chamadas em linguagens como Python.

Algoritmo

Crie uma tabela dp de zeros com dimensões (n+1) × (m+1).
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]

Manter apenas duas linhas

Intuição

A linha i da tabela lê apenas a linha i-1 e suas próprias células anteriores. Quando uma linha é concluída, nenhuma linha acima dela é lida novamente. Portanto, mantenha dois vetores, prev para a linha concluída e cur para a linha que está sendo preenchida, e troque-os após cada linha. A recorrência e a ordem permanecem exatamente iguais.

Uma subsequência comum de duas strings não depende de qual string vem primeiro, então você pode trocá-las e fazer as linhas percorrerem a string mais curta. Cada linha terá então 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 de trabalho.

A primeira entrada de cada linha representa um prefixo vazio da string mais curta, então deve permanecer 0. A resposta é a última entrada da última linha concluída.

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

A recorrência é curta, e a maioria dos bugs ocorre por um erro de uma unidade ou por adicionar uma correspondência no lugar errado.

Confundir os índices da tabela com os índices da string. A célula dp[i][j] compara text1[i-1] com text2[j-1], porque a linha 0 representa o prefixo vazio.
Em uma correspondência, adicionar 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 em relação a a retornaria 2 em vez de 1.
Fazer correspondências de forma gulosa com dois ponteiros. cab em relação a abc combina as duas letras c e retorna 1, enquanto ab resulta em 2.
Escrever na linha que você ainda está lendo. Ao usar duas linhas, todo valor da linha acima deve vir de prev, e cur[0] deve permanecer 0.
Resolver por engano o problema da substring comum mais longa. Uma subsequência pode pular letras; uma substring não pode.
Usar memoização com recursão em strings de 1000 letras. A profundidade das chamadas chega a 2000, ultrapassando o limite padrão de 1000 do Python.

Perguntas frequentes4

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

A solução com tabela é executada em tempo O(n × m), em que n e m são os dois comprimentos: ela preenche uma célula para cada par de prefixos. Ela precisa de O(n × m) de memória para a tabela completa, ou O(min(n, m)) usando duas linhas. A recursão simples sem uma tabela tem complexidade exponencial.

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

Uma subsequência pode pular letras, desde que a ordem seja mantida, enquanto 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 versão de substring usa uma tabela semelhante, mas uma incompatibilidade redefine a célula para 0 em vez de copiar uma célula vizinha.

Como imprimir a própria subsequência comum mais longa?

Preencha a tabela inteira e, em seguida, volte a partir de dp[n][m]. Quando as duas letras na célula atual forem iguais, essa letra fará parte da resposta: registre-a e avance na diagonal para cima e para a esquerda. Caso contrário, avance para a célula vizinha acima ou à esquerda que contenha o maior valor. Inverta as letras registradas no final. A versão com duas linhas não consegue fazer isso, pois descartou as linhas anteriores.

Como a LCS está relacionada às ferramentas diff e à distância de edição?

Uma comparação entre duas versões de um arquivo encontra a maior subsequência comum de suas linhas; cada linha fora dela é exibida como adicionada ou removida. Da mesma forma, o menor número de inserções e exclusõ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, por isso usa sua própria tabela, com uma terceira opção por célula.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

text1 = "stone"
text2 = "longest"

Esperado

Longest Common Subsequence

Função

Restrições

Exemplos

Dicas

Solução

Compare as primeiras letras com recursão

Preencha uma tabela de prefixos

Manter apenas duas linhas

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos