Minimum Edit Distance

You are 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:

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

This problem can be solved using dynamic programming. Define a DP table \(dp\) where \(dp[i][j]\) is the minimum edit distance between the first \(i\) characters of s1 and the first \(j\) characters of s2. The recurrence can be written in LaTeX format as:

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

Your program should read the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains the string s1, and the second line contains the string s2.

outputFormat

Output a single integer representing the minimum edit distance between s1 and s2.## sample

horse
ros

3