Pular para o conteúdo

Menos remoções para igualar palavras

Fácil#lcs#string-dp~20 min

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

Tempo-alvo
O(m · n)
Espaço-alvo
O(m · n)

Travou na ideia, e não no código? Maior subsequência comum explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado