Minimum Edit Distance

Given two strings S and T, your task is to compute the minimum number of operations required to convert S into T. The allowed operations are:

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

You are expected to solve this problem using dynamic programming. The recurrence relation is given by:

$$ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] & \text{if } S[i-1] = T[j-1] \\ \min\Big(\text{dp}[i-1][j] + 1,\; \text{dp}[i][j-1] + 1,\; \text{dp}[i-1][j-1] + 1\Big) & \text{otherwise} \end{cases} $$

for \(1 \le i \le |S|\) and \(1 \le j \le |T|\), with the base cases:

$$ \text{dp}[i][0] = i \quad \text{and} \quad \text{dp}[0][j] = j. $$

Calculate and output the minimum 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 S and T are non-empty strings made up of lowercase letters (they could be empty as well).

outputFormat

Output a single integer representing the minimum number of operations required to convert S into T.

## sample

horse
ros

3