Levenshtein Distance

Given two strings, compute the Levenshtein distance between them. The Levenshtein distance is defined as the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into the other. The distance can be computed using the following recurrence:

$$ D(i,j)=\min\begin{cases} D(i-1,j)+1,\\ D(i,j-1)+1,\\ D(i-1,j-1)+\begin{cases}0,&\text{if } s_1[i]=s_2[j],\\1,&\text{otherwise} \end{cases} \end{cases} $$ where s₁ and s₂ are the input strings.

inputFormat

The input consists of two lines. The first line contains the first string, and the second line contains the second string.

outputFormat

Output a single integer that represents the Levenshtein distance between the two given strings.

kitten
sitting

3