Minimum Edit Distance

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

• Insertion
• Deletion
• Substitution

This problem can be solved using dynamic programming. Formally, if we denote the edit distance by \(D(i,j)\) between the first \(i\) characters of s1 and the first \(j\) characters of s2, the recurrence is:

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

Compute \(D(m,n)\) where \(m\) and \(n\) are the lengths of s1 and s2 respectively.

inputFormat

The input consists of two lines:

1. The first line contains the string s1.
2. The second line contains the string s2.

Both strings may be empty.

outputFormat

Output a single integer representing the minimum number of operations required to convert s1 to s2.

## sample

horse
ros

3

</p>