Edit Distance Computation

This problem requires you to compute the edit distance (also known as the Levenshtein distance) between two given strings using dynamic programming. The edit distance is defined as the minimum number of operations (insertions, deletions, or substitutions) required to transform one string into the other.

You should implement the following relation using dynamic programming:

$$dp[i][j] = \begin{cases} j & \text{if } i=0,\\ i & \text{if } j=0,\\ dp[i-1][j-1] & \text{if } s_1[i-1]=s_2[j-1],\\ 1+\min\{dp[i-1][j],\;dp[i][j-1],\;dp[i-1][j-1]\} & \text{otherwise.} \end{cases}$$

Your program must read the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains the first string s₁ and the second line contains the second string s₂. The strings may be empty and will not contain spaces.

outputFormat

Output a single integer representing the edit distance between the two strings.

kitten
sitting

3