Minimum Edit Distance Transformation

Given two strings S1 and S2, compute the minimum number of operations needed to convert S1 into S2 using the following operations:

• Insertion of a single character
• Deletion of a single character
• Substitution (replacement) of one character with another

This problem is a classical Edit Distance (or Levenshtein distance) problem and can be solved efficiently using dynamic programming. The recurrence relation is given in LaTeX as:

\( dp[i][j] = \min \begin{cases} dp[i-1][j] + 1, \\ dp[i][j-1] + 1, \\ dp[i-1][j-1] + \mathbb{1}(S1[i-1] \neq S2[j-1]) \end{cases} \)

where \( dp[i][j] \) represents the minimum operations required to convert the first \( i \) characters of S1 to the first \( j \) characters of S2, and \( \mathbb{1}(\cdot) \) is the indicator function.

inputFormat

The input is read from standard input (stdin). The first line contains the string S1, and the second line contains the string S2. Both strings can be empty.

outputFormat

Output to standard output (stdout) a single integer representing the minimum number of operations required to transform S1 into S2.## sample

horse
ros

3