Minimum Edit Operations

You are given two strings. Your task is to compute the minimum number of edit operations required to transform the first string into the second string. The allowed operations are:

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

Mathematically, let \( dp[i][j] \) represent the minimum number of operations needed to convert the first \( i \) characters of the first string to the first \( j \) characters of the second string. 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_1[i] = s_2[j]\\ 1 + \min\{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]\}, & \text{otherwise} \end{cases} \]

Compute and output \( dp[m][n] \), where \( m \) and \( n \) are the lengths of the first and second strings respectively.

inputFormat

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

outputFormat

Output a single integer representing the minimum number of operations required to convert the first string into the second string.## sample

abc
def

3