Edit Distance Transformation

Problem Statement:

Given two strings A and B, determine the minimum number of operations required to transform string A into string B. The allowed operations are insertion, deletion, and substitution of a single character. This is a classical problem of computing the edit distance between two strings.

Formal Definition:

Let \(dp[i][j]\) be the minimum number of operations required to transform the first \(i\) characters of string A into the first \(j\) characters of string B. Then, the recurrence is given by:

\[ \begin{aligned} dp[i][0] &= i, \\ dp[0][j] &= j, \\ dp[i][j] &= \begin{cases} dp[i-1][j-1] & \text{if } A_i = B_j, \\ \min\{dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]\} + 1 & \text{if } A_i \neq B_j. \end{cases} \end{aligned} \]

Your task is to implement a program that reads two strings from the standard input and prints the minimum number of operations (edit distance) needed to transform the first string into the second string.

Examples:

• Input: abcd and abcde → Output: 1
• Input: abc and xyz → Output: 3

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains the string A and the second line contains the string B. Note that the strings may be empty.

outputFormat

The output is printed to standard output (stdout) as a single integer representing the minimum number of operations required to transform string A into string B.## sample

abcd
abcde

1