Edit Distance (Distanza di modifica)
L’edit distance tra due stringhe è il numero minimo di operazioni richieste per trasformare una stringa nell’altra. Le operazioni consentite sono:
- Aggiungere un carattere alla stringa.
- Rimuovere un carattere dalla stringa.
- Sostituire un carattere nella stringa.
Ad esempio, l’edit distance tra e è 2, perché prima si può sostituire con e poi aggiungere .
Date due stringhe, il tuo obiettivo è calcolare la edit distance tra di esse.
Input (Ingresso)
La prima riga di input contiene la prima stringa, mentre la seconda riga contiene la seconda stringa. È garantito che il numero di caratteri delle stringhe non superi 1000.
Output (Uscita)
Il programma deve stampare un unico intero: la edit distance tra le due stringhe fornite.
Esempi
Input | Output |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB