Dadas duas strings a e b, retorne o tamanho da maior subsequência comum às duas.
Se não existir nenhuma, retorne 0.
Uma subsequência é o que sobra de uma string depois de apagar zero ou mais caracteres, sem mudar a ordem
dos que ficaram. "ACE" é subsequência de "ABCDE", mas "AEC" não é. Diferente de uma substring, os caracteres não
precisam estar colados.
Exemplo 1 · a = "ABDCB", b = "ACBC" → 3
"ABC" aparece nas duas, nessa ordem: ABDCB e ACBC. Não existe nenhuma comum de tamanho 4.
Exemplo 2 · a = "GATO", b = "PATO" → 3
"ATO": só a primeira letra muda.
Exemplo 3 · a = "ABC", b = "XYZ" → 0
Nenhum caractere em comum.
Restrições: 1 ≤ a.length, b.length ≤ 1000 · as strings só têm letras
Tabulation: dp[i][j] = tamanho da LCS dos prefixos a[0..i) e
b[0..j). A linha 0 e a coluna 0 são a string vazia, então valem 0. Olhe o último caractere de cada prefixo:
· iguais: ele entra na LCS → diagonal + 1 (dp[i-1][j-1] + 1).
· diferentes: um dos dois sobra. Descarta o de a (cima, dp[i-1][j])
ou o de b (esquerda, dp[i][j-1]) e fica com o maior.
A tabela só dá o tamanho. Para saber qual é a subsequência, o final do código faz o
caminho de volta: sai de dp[m][n] e pergunta de onde cada valor veio.
tempo O(m·n)espaço O(m·n)
Uma célula por par de prefixos. O caminho de volta soma só O(m + n).
a = "ABDCB" · b = "ACBC"
caractere de acaractere de bprefixo já cobertoentrou na LCS
registradores
tabela dp[i][j]
diagonal · ou cimaesquerdaescritacaminho de volta
código
memória · bloco contíguo row-major
(m+1)·(n+1) células: O(m·n) de espaço. É o preço de poder refazer o caminho no final: a versão com
array economiza memória, mas perde a tabela e só sabe o tamanho.
A matriz lê três vizinhos: dp[i-1][j] (cima),
dp[i][j-1] (esquerda) e dp[i-1][j-1] (diagonal). Com uma só linha percorrida para
frente, cima e esquerda saem de graça: dp[j] ainda é da linha antiga e dp[j-1] já é da nova.
O problema é a diagonal: ela era o dp[j-1] antigo, que acabou de ser
sobrescrito. O truque: antes de escrever em dp[j], guardar o valor antigo em tmp. No fim da
coluna, prev = tmp, e esse valor é exatamente a diagonal que a coluna j+1 vai precisar. Sem o
prev, o "diagonal + 1" leria o valor errado.
tempo O(m·n)espaço O(n)
Mesmas contas; uma linha de n + 1 células mais a variável prev.
a = "ABDCB" · b = "ACBC"
caractere de acaractere de bprefixo já coberto
registradores
array dp[j] + prev + tmp
prev (diagonal) · ou dp[j] antigo (cima)dp[j-1] novo (esquerda)escritai=k linha da matriz que a célula representa
código
memória · O(n)
n+1 células + 2 variáveis, independente do tamanho de a. A matriz usaria (m+1)·(n+1). Dica: use
como b a string menor.
Memoization (top-down): f(i, j) = tamanho da LCS dos sufixosa[i..] e b[j..]. Se os primeiros caracteres são iguais, ele entra na LCS e os dois avançam
(1 + f(i+1, j+1)). Senão, tenta descartar um de cada lado e fica com o melhor:
max(f(i+1, j), f(i, j+1)). Os dois descartes acabam pedindo os mesmos sufixos (ex.: os dois chegam em
f(i+1, j+1)), por isso o memo. Sem ele seriam O(2^(m+n)) chamadas, com ele O(m·n).
tempo O(m·n)espaço O(m·n)
Cada f(i, j) é calculado uma vez. Memo m×n e call stack de até m + n frames.
a = "ABDCB" · b = "ACBC"
caractere de acaractere de bsufixo ainda por resolver
registradores
memo[i][j]
leitura · cache hitescrita░░ nunca calculado
código
call stack
memória · heap (memo)
Quando os caracteres casam, só um ramo é chamado. Por isso várias células nunca são calculadas.
Os casos base (um sufixo vazio) não ocupam o memo: ele tem m·n células, não (m+1)·(n+1).