Edit Distance

Given two strings S and T, compute the minimum number of edit operations required to transform string S into string T. The allowed operations are:

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

In other words, if we denote the edit distance by \(dp[i][j]\) which is the minimum number of operations needed to convert the first \(i\) characters of S to the first \(j\) characters of T, then the recurrence is given by:

\(dp[i][j] = \begin{cases} j, & i = 0\\ i, & j = 0\\ dp[i-1][j-1], & S[i] = T[j] \\ 1+\min\{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]\}, & \text{otherwise} \end{cases}\)

Your task is to implement an algorithm to compute this edit distance.

inputFormat

The input consists of two lines read from standard input. The first line contains the source string S and the second line contains the target string T.

outputFormat

Output a single integer to standard output, representing the minimum number of operations required to transform S into T.

kitten
sitting

3