Edit Distance: Transforming Strings with Minimum Operations

In this problem, you are given two strings S₁ and S₂. Your task is to compute the minimum number of operations required to transform S₁ into S₂ using the following operations:

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

The problem can be mathematically formulated using dynamic programming. The recurrence relation 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_1[i-1] = S_2[j-1],\\ 1+\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) & \text{otherwise.} \end{cases} $$ where dp[i][j] represents the minimum edit distance between the first i characters of S₁ and the first j characters of S₂.

Your solution must read input from standard input (stdin) and output the answer to standard output (stdout) in a single line.

inputFormat

The input consists of two lines. The first line contains the string S₁ and the second line contains the string S₂. Both strings may be empty.

outputFormat

Output a single integer which represents the minimum number of operations required to convert S₁ into S₂.

kitten
sitting

3