Minimum Edit Distance Transformation

You are given two strings, s1 and s2. Your task is to compute the minimum number of operations required to transform s1 into s2 using the following operations:

• Insertion: Add a character.
• Deletion: Remove a character.
• Replacement: Replace one character with another.

The problem can be formulated using the following recurrence in LaTeX:

$$\text{dp}[i][j]=\begin{cases} i & \text{if } j=0,\\ j & \text{if } i=0,\\ \text{dp}[i-1][j-1] & \text{if } s1[i-1]=s2[j-1],\\ 1 + \min\{\text{dp}[i-1][j],\text{dp}[i][j-1],\text{dp}[i-1][j-1]\} & \text{if } s1[i-1]\neq s2[j-1]. \end{cases} $$

The final answer will be dp[m][n] where m is the length of s1 and n is the length of s2.

inputFormat

The input consists of two lines. The first line contains the string s1, and the second line contains the string s2. Both strings may be empty.

outputFormat

Output a single integer which represents the minimum number of operations required to transform s1 into s2.## sample

kitten
sitting

3