Saltar al contenido

Menos borrados para igualar dos palabras

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

La misión

Problema

Dadas dos palabras a y b, un paso elimina un solo carácter de cualquiera de las dos. Devuelve la menor cantidad de pasos necesaria para que las dos palabras sean idénticas.

Ejemplos

Input:  a = "sea", b = "eat"
Output: 2
Por qué: eliminas la s de sea y la t de eat, y queda ea en ambas
Input:  a = "abcde", b = "ace"
Output: 2
Por qué: ace ya aparece dentro de abcde en orden, así que solo se van la b y la d
Input:  a = "abc", b = ""
Output: 3
Por qué: caso límite: hay que eliminar todo lo de la primera palabra

Pistas

0 / 3

Tiempo objetivo
O(m · n)
Espacio objetivo
O(m · n)

¿Lo que te frena es la idea y no el código? Subsecuencia común más larga lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio