Minimum Edit Distance Operations

You are given two strings S1 and S2. Your task is to compute the minimum number of operations required to convert S1 into S2.

The allowed operations are:

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

The problem can be formulated using dynamic programming. In particular, if we define dp(i, j) as the minimum number of operations to convert the first i characters of S1 to the first j characters of S2, the recurrence is given by:

\(dp(i,j)=\begin{cases} i & j=0\\ j & i=0\\ dp(i-1,j-1) & S1_i=S2_j \\ \min\{dp(i-1,j),\;dp(i,j-1),\;dp(i-1,j-1)\}+1 & \text{otherwise} \end{cases}\)

Use this relation (or an equivalent approach) to compute the result.

inputFormat

The input is read from stdin and consists of two lines. The first line contains the string S1 and the second line contains the string S2.

outputFormat

Output a single integer to stdout representing the minimum number of operations required to convert S1 into S2.## sample

kitten
sitting

3