Minimum Edit Distance

Given two strings s and t, determine the minimum number of operations required to convert s into t. The allowed operations are:

• Insertion of a character
• Deletion of a character
• Substitution of one character for another

The solution may be computed using dynamic programming. Define a 2D table \(dp\) where \(dp[i][j]\) is the minimum number of operations required to convert the first \(i\) characters of s to the first \(j\) characters of t. The recurrence is given by:

[ dp[i][j]=\begin{cases} j, & \text{if } i=0,\ i, & \text{if } j=0,\ dp[i-1][j-1], & \text{if } s[i-1]=t[j-1],\ 1+\min{dp[i][j-1],; dp[i-1][j],; dp[i-1][j-1]}, & \text{if } s[i-1]\neq t[j-1]. \end{cases} ]

Your task is to implement an efficient algorithm to compute \(dp[m][n]\) where \(m\) and \(n\) are the lengths of the input strings.

inputFormat

The input is provided via stdin and consists of exactly two lines:

1. The first line contains the source string s.
2. The second line contains the target string t.

outputFormat

Output a single integer to stdout, representing the minimum number of operations required to convert s into t.

abcdef
azced

3