Minimum Edit Distance

Given two strings s and t, your task is to compute the minimum number of operations required to convert string s into string t. You are allowed to perform the following three operations:

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

This problem is a classic application of dynamic programming. Let \(dp[i][j]\) denote the minimum edit distance between the first \(i\) characters of s and the first \(j\) characters of t. The recurrence relation is given by:

$$ \begin{array}{ll} \text{If } i = 0: & dp[i][j] = j, \\ \text{If } j = 0: & dp[i][j] = i, \\ \text{If } s[i-1] = t[j-1]: & dp[i][j] = dp[i-1][j-1], \\ \text{Otherwise}: & dp[i][j] = 1 + \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]). \end{array} $$

Compute and output \(dp[m][n]\) where \(m\) and \(n\) are the lengths of strings s and t respectively.

inputFormat

The input consists of two lines. The first line contains the string s, and the second line contains the string t.

outputFormat

Output a single integer representing the minimum edit distance to convert s into t.

## sample

horse
ros

3

</p>