Edit Distance Problem

Given two strings, compute the edit distance between them. The edit distance is defined as the minimum number of single-character edits (insertions, deletions or substitutions) required to change one string into the other.

The recurrence relation for the dynamic programming solution is as follows:

[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1], & \text{if } s_1[i-1] = s_2[j-1] \ 1 + \min\bigl{\text{dp}[i-1][j],, \text{dp}[i][j-1],, \text{dp}[i-1][j-1]\bigr}, & \text{if } s_1[i-1] \neq s_2[j-1] \end{cases} ]

You are required to implement an algorithm to compute the edit distance based on the above definition. The input will be provided from standard input (stdin) and the output should be printed to standard output (stdout).

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 representing the edit distance between the two strings.## sample

kitten
sitting

3