Minimum Edit Operations

Given two strings, a source and a target, determine the minimum number of operations required to convert the source string into the target string. The allowed operations are:

• Insert a character.
• Remove a character.
• Replace a character with another.

Let \(D(i,j)\) be the minimum edit distance between the first \(i\) characters of the source and the first \(j\) characters of the target. The recurrence is defined as:

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

This problem requires you to implement the above logic using dynamic programming.

inputFormat

The input consists of two lines:

1. The first line is the source string.
2. The second line is the target string.

outputFormat

Output a single integer representing the minimum number of operations required to convert the source string into the target string.

## sample

kitten
sitting

3