Maior Subsequência Comum
Alinhe duas strings com uma tabela de DP.
Maior Subsequência Comum é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é uma subsequência
Uma subsequência mantém os caracteres na mesma ordem, mas pode ignorar alguns. De 'abcde', você pode obter 'ace', mas nunca 'aec'.
O objetivo do LCS
Dadas duas cadeias de caracteres, a subsequência comum mais longa é a maior sequência que aparece em ambas, mantendo a mesma ordem relativa.
Passe para uma grade
Compare os prefixos das duas cadeias de caracteres. Uma tabela bidimensional baseada nos comprimentos delas transforma isso em uma DP de grade familiar.
Defina o estado
Considere dp[i][j] como o comprimento da LCS dos primeiros i caracteres de A e dos primeiros j caracteres de B.
Quando os caracteres coincidem
Se A[i-1] for igual a B[j-1], essa letra compartilhada amplia a LCS. Some um ao valor da diagonal dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Quando eles são diferentes
Se as letras forem diferentes, descarte um caractere de qualquer uma das cadeias e mantenha o melhor resultado. Escolha o máximo dos dois vizinhos.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])O caso base
Um prefixo vazio não compartilha nada, portanto o comprimento da LCS é zero. A linha 0 e a coluna 0 permanecem cheias de zeros.
dp = [[0] * (m+1) for _ in range(n+1)]Uma linha e uma coluna extras
Dimensionar a tabela como n+1 por m+1 fornece uma borda de zeros sem custo adicional. Isso elimina verificações de limites incômodas nas extremidades.
Preencha tudo
Percorra i e j começando em 1. Cada célula precisa apenas dos valores acima, à esquerda e na diagonal, que já foram calculados.
for i in range(1, n+1):
for j in range(1, m+1):
...Leia o comprimento
O comprimento completo da LCS fica no canto. A resposta é dp[n][m] quando todas as células estiverem preenchidas.
length = dp[n][m]Complexidade
Você acessa cada célula uma vez, portanto o trabalho exige O(n vezes m) de tempo e memória. Isso lida tranquilamente com cadeias de até alguns milhares de caracteres.
Verificação rápida
Os caracteres atuais A[i-1] e B[j-1] são iguais. Qual atualização está correta?
Recapitulação: LCS
Construa uma tabela de n+1 por m+1: quando houver coincidência, some um à diagonal; caso contrário, escolha o vizinho máximo. O canto contém o comprimento. 🔗
Perguntas Frequentes
A aula “Maior Subsequência Comum” é grátis?
Sim — o texto completo de “Maior Subsequência Comum” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Maior Subsequência Comum”?
Alinhe duas strings com uma tabela de DP. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Maior Subsequência Comum”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Contagem de Caminhos em uma Grade
- Soma Mínima de Caminho com Obstáculos
- Maior Subsequência Comum
- Distância de Edição Passo a Passo