Distancia de Edición
La distancia de edición entre dos cadenas es la cantidad mínima de operaciones necesarias para transformar una cadena en la otra. Las operaciones permitidas son:
- Añadir un carácter a la cadena.
- Eliminar un carácter de la cadena.
- Reemplazar un carácter de la cadena.
Por ejemplo, la distancia de edición entre y es 2, porque primero se puede reemplazar por y luego añadir .
Dadas dos cadenas, tu tarea es calcular la distancia de edición entre ellas.
Input
La primera línea de la entrada contiene la primera cadena, mientras que la segunda línea contiene la segunda cadena. Se garantiza que la cantidad de caracteres en ambas cadenas no excede 1000.
Output
El programa debe imprimir un número entero: la distancia de edición entre las dos cadenas dadas.
Examples
Entrada | Salida |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB