Minimum Edit Distance

Given two strings s and t, your task is to compute the minimum number of operations required to transform s into t. The permitted operations are:

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

Each operation incurs a cost of 1. The answer may be computed using the dynamic programming approach based on the recurrence:

\( 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-1][j], dp[i][j-1], dp[i-1][j-1]) & \text{otherwise.} \end{cases} \)

For example, transforming "intention" into "execution" requires 5 operations.

inputFormat

The input consists of two lines. The first line contains the string s and the second line contains the string t.

Both strings can be empty and will consist of printable characters.

outputFormat

Output a single integer representing the minimum number of operations required to transform string s into string t.

intention
execution

5