Minimum Edit Operations

You are given two strings s1 and s2. Your task is to determine the minimum number of operations required to transform s1 into s2. The allowed operations are:

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

This problem is a classic dynamic programming problem referred to as the Edit Distance problem. The recurrence relation can be written in LaTeX as:

$$ \text{dp}[i][j] = \begin{cases} j, &\text{if } i=0\\ i, &\text{if } j=0\\ \text{dp}[i-1][j-1], &\text{if } s1[i-1]=s2[j-1]\\ 1+\min(\text{dp}[i-1][j],\, \text{dp}[i][j-1],\, \text{dp}[i-1][j-1]), &\text{otherwise} \end{cases} $$

For example, transforming "kitten" into "sitting" requires 3 operations.

inputFormat

The input consists of two lines. The first line contains the string s1 and the second line contains the string s2. Both strings may be empty.

outputFormat

Output a single integer representing the minimum number of operations required to convert s1 into s2.

abc
yabd

2