Menos remoções para igualar palavras
A missão
Problema
Dadas duas palavras a e b, um passo apaga um único caractere de qualquer uma das palavras. Retorne o menor número de passos necessário para deixar as duas palavras idênticas.
Exemplos
Input: a = "sea", b = "eat"
Output: 2
Por quê: apague o s de sea e o t de eat, sobrando ea nas duas
Input: a = "abcde", b = "ace"
Output: 2
Por quê: ace já aparece dentro de abcde em ordem, então só b e d saem
Input: a = "abc", b = ""
Output: 3
Por quê: edge case: tudo na primeira palavra precisa ser apagado
Dicas
0 / 3
O que sobra depois das remoções aparece nas duas palavras, na mesma ordem. Qual é o máximo que você poderia manter?
Os caracteres que você mantém formam uma subsequência comum das duas palavras. Manter a maior subsequência comum (LCS) significa apagar o mínimo possível.
Calcule o tamanho da maior subsequência comum com uma tabela em que a entrada (i, j) cobre os primeiros i caracteres de a e os primeiros j de b. A resposta é len(a) + len(b) menos o dobro desse tamanho.
- Tempo-alvo
- O(m · n)
- Espaço-alvo
- O(m · n)
Solução
Apagar até as palavras ficarem iguais deixa uma string que é subsequência das duas, então o menor número de remoções vem de manter a maior subsequência comum e remover todo o resto de cada palavra. A entrada da tabela para os primeiros i caracteres de a e os primeiros j de b estende em um a entrada da diagonal quando os últimos caracteres são iguais e, caso contrário, pega o melhor entre descartar o último caractere de uma ou da outra palavra. Todo caractere fora da subsequência comum é apagado uma vez, o que dá len(a) + len(b) - 2 * lcs. O tempo é O(m · n) e o espaço é O(m · n) para palavras de tamanhos m e n.
def min_deletions(a, b):
m, n = len(a), len(b)
lcs = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
lcs[i][j] = lcs[i - 1][j - 1] + 1 # keep the matching pair
else:
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
return m + n - 2 * lcs[m][n] # delete everything not kept
print(min_deletions("sea", "eat")) # -> 2
print(min_deletions("abcde", "ace")) # -> 2
print(min_deletions("abc", "")) # -> 3Travou na ideia, e não no código? Maior subsequência comum explica isso.