Edit Distance Problem

Given two strings s₁ and s₂, your task is to compute the minimum number of edit operations needed to transform s₁ into s₂. In one operation, you can:

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

This problem is equivalent to finding the Levenshtein distance between the two strings. The recurrence relation for the dynamic programming solution is given by:

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

where \(dp(i,j)\) is the edit distance between the first \(i\) characters of s₁ and the first \(j\) characters of s₂.

inputFormat

The input consists of two lines:

1. The first line contains the string s₁.
2. The second line contains the string s₂.

Note: The strings can be empty.

outputFormat

Output a single integer, which is the minimum number of edit operations required to convert s₁ into s₂.

## sample

horse
ros

3