Minimum Edit Distance

You are given two strings, A (the source) and B (the target). Your task is to compute the minimum number of operations required to convert A into B using the following operations:

• Insertion: Insert a single character.
• Deletion: Delete a single character.
• Replacement: Replace one character with another.

The solution can be achieved via dynamic programming. Formally, let \(dp[i][j]\) denote the minimum number of operations required to convert the first \(i\) characters of A into the first \(j\) characters of B. 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 } A[i] = B[j], \\ 1 + \min\{dp[i][j-1],\; dp[i-1][j],\; dp[i-1][j-1]\} & \text{if } A[i] \neq B[j]. \end{cases}\)

Your program should read the input from stdin and output the answer to stdout.

inputFormat

The input consists of two lines. The first line contains the source string A. The second line contains the target string B. Both strings may be empty.

outputFormat

Output a single integer representing the minimum number of operations needed to transform string A into string B.## sample

kitten
sitting

3