Minimum Edit Distance

Minimum Edit Distance

You are given two strings A and B. Your task is to compute the minimum number of operations required to transform string A into string B. In one operation, you may insert a character, delete a character, or replace a character.

The edit distance (also known as the Levenshtein distance) is computed using the following formula: $$ dp[i][j] = \min\begin{cases} dp[i-1][j] + 1 \\ dp[i][j-1] + 1 \\ dp[i-1][j-1] + \begin{cases} 0 & \text{if } A[i-1]=B[j-1] \\ 1 & \text{if } A[i-1] \neq B[j-1] \end{cases} \end{cases} $$ where $dp[i][j]$ represents the edit distance between the first $i$ characters of A and the first $j$ characters of B.

Please implement a program that reads two strings from standard input and outputs the minimum edit distance to standard output.

inputFormat

The input consists of two lines:

• The first line contains the string A.
• The second line contains the string B.

Both strings consist of lowercase English letters with length not exceeding 500.

outputFormat

Output a single integer representing the minimum number of operations required to convert A into B.

## sample

kitten
sitting

3

</p>