Minimum Edit Distance

You are given two strings str1 and str2. Your task is to compute the minimum number of operations required to convert str1 into str2. The allowed operations are:

• Insertion of a character
• Deletion of a character
• Replacement of a character

This is a classic dynamic programming problem known as the Edit Distance problem.

The recurrence relation can be expressed in LaTeX as follows:

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

inputFormat

The input is read from standard input. The first line contains the string str1 and the second line contains the string str2. Both strings consist of lowercase letters.

outputFormat

Output to standard output a single integer representing the minimum number of operations required to convert str1 into str2.## sample

kitten
sitting

3