Minimum Edit Operations

Given two strings A and B, your task is to determine the minimum number of operations required to convert string A into string B. The allowed operations are:

• Insert a character.
• Delete a character.
• Replace a character.

The solution should calculate the minimum number of these operations needed. The algorithm typically uses a dynamic programming approach. The edit distance is formally defined as follows:

\( dp[i][j] = \min\begin{cases} dp[i-1][j] + 1, & \text{(delete)}\\ dp[i][j-1] + 1, & \text{(insert)}\\ dp[i-1][j-1] + \mathbf{1}_{(A[i-1] \neq B[j-1])}, & \text{(replace)} \end{cases} \)

Read the two input strings from standard input (stdin) and write the minimum number of operations to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains the string A and the second line contains the string B.

outputFormat

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

kitten
sitting

3