Solução de Frederico Bulhões
Para resolver esse problema devemos encontrar a maior subsequência comum entre os dois vetores. Depois de encontrado esse valor, podemos então imprimir $$n-val$$ e $$m-val$$, a quantidade de modificações para tornar um vetor equivalente ao outro. Para calular o LCS (longest common substring) podemos fazer a seguinte recorrência, nos vetores a, b:
$$LCS(i, j) = $$
- se $$a[i] = b[j]$$:
- $$1+LCS(i+1, j+1)$$
- se $$a[i] != b[j]$$:
- $$max(LCS(i, j+1), LCS(i+1, j))$$
E também levamos em conta os casos base, quando $$i > n$$ ou $$j > m$$, em que a resposta será zero.
Podemos então usar programação dinâmica, e gravar os resultados para $$LCS(i,j))$$ em uma tabela e evitar computarmos duas vezes o mesmo resultado.
Código para melhor entendimento:
https://gist.github.com/fredbr/fbde2ae31f60b6fd5dfe2c5a0c023802
Deixe um comentário