Edit Distance

You are given two strings s and t. Your task is to compute the minimum number of operations required to transform s into t.

You are allowed to perform the following operations on the string:

• Insert a character
• Delete a character
• Replace a character

This is a classic dynamic programming problem. One can formulate the recurrence relation as follows:

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

Implement an algorithm to calculate this edit distance.

inputFormat

The input consists of two lines:

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

Both strings may be empty.

outputFormat

Output a single integer, which is the minimum number of operations required to transform s into t.

## sample

horse
ros

3

</p>