Edit Distance
The edit distance between two strings is the minimum number of operations required to transform one string into the other. The allowed operations are:
- Add one character to the string.
- Remove one character from the string.
- Replace one character in the string.
For example, the edit distance between and is 2, because you can first replace with , and then add .
Given two strings, your task is to calculate the edit distance between two strings.
Input
The first line of the input contains the first string, while the second line contains the second string. It’s guaranteed that the number of characters in the strings does not exceed 1000.
Output
The program should print a single integer - the edit distance between the two given strings.
Examples
Input | Output |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB