Minimum Edit Distance

You are given two strings, S and T. Your task is to determine the minimum number of operations needed to transform S into T. The allowed operations are:

• Insert a character at any position.
• Delete a character from any position.
• Replace a character with another character.

The problem can be solved using dynamic programming. In particular, let \(dp[i][j]\) be the minimum edit distance between the first \(i\) characters of S and the first \(j\) characters of T. The recurrence is given by:

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

Your program should read the two strings from standard input and print the minimum number of operations to standard output.

inputFormat

The input consists of two lines: The first line contains the string S. The second line contains the string T. Both strings consist of lowercase English letters and may be empty.

outputFormat

Output a single integer representing the minimum number of operations required to transform string S into string T.## sample

horse
ros

3