Edit Distance Calculation

You are given two strings s1 and s2. Your task is to compute the minimum number of operations required to transform s1 into s2. The allowed operations are:

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

The problem is a classic example of computing the Edit Distance between two strings. Mathematically, if we define dp[i][j] as the minimum number of operations to convert the first i characters of s1 into the first j characters of s2, then the recurrence relation can be written in LaTeX as:

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

Your program should read the input from standard input and write the output to standard output.

inputFormat

The input consists of two lines. The first line contains the string s1, and the second line contains the string s2. Both strings consist of lowercase letters and may be empty.

outputFormat

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

horse
ros

3