8576: DPL_1_E : Edit Distance (Levenshtein Distance)
[Creator : ]
Description
Find the edit distance between given two words $s_1$ and $s_2$.
The disntace is the minimum number of single-character edits required to change one word into the other. The edits including the following operations:
- insertion: Insert a character at a particular position.
- deletion: Delete a character at a particular position.
- substitution: Change the character at a particular position to a different character
Input
Two words $s_1$ and $s_2$ are given in the first line and the second line respectively. The words will consist of lower case characters.
Output
Print the edit distance in a line.
Constraints
$1 ≤ |s_1| ≤ 1000$
$1 ≤ |s_2| ≤ 1000$
$1 ≤ |s_2| ≤ 1000$
Sample 1 Input
acac
acm
Sample 1 Output
2
Sample 2 Input
icpc
icpc
Sample 2 Output
0