Minimum Edit Distance

Given two strings \(s_1\) and \(s_2\), compute the minimum number of operations required to transform \(s_1\) into \(s_2\). The allowed operations are:

• Insertion of a character
• Deletion of a character
• Substitution of a character

Each operation has a cost of 1. Formally, let \(D(i,j)\) be the minimum edit distance between the first \(i\) characters of \(s_1\) and the first \(j\) characters of \(s_2\). The recurrence relation is given by:

\[ D(i,j)=\begin{cases} i & \text{if } j=0,\\ j & \text{if } i=0,\\ D(i-1,j-1) & \text{if } s_1[i]=s_2[j],\\ 1+\min\{D(i-1,j),\; D(i,j-1),\; D(i-1,j-1)\} & \text{otherwise.} \end{cases} \]

Your task is to implement this using dynamic programming. This is a classic problem in competitive programming and tests your ability to apply DP on strings.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains the string \(s_1\).
2. The second line contains the string \(s_2\).

Both strings may be empty and consist of lowercase English letters.

outputFormat

Output a single integer to stdout which represents the minimum number of operations required to transform \(s_1\) into \(s_2\) using insertion, deletion, or substitution.

## sample

horse
ros

3

</p>