Edit Distance Transformation

You are given two strings: an initial string and a target string. Your task is to determine the minimum number of operations required to transform the initial string into the target string. The allowed operations are insertion, deletion, and replacement of a single character.

This problem can be solved using dynamic programming. Let \(dp[i][j]\) denote the minimum number of operations needed to convert the first \(i\) characters of the initial string to the first \(j\) characters of the target string. The recurrence is defined as follows:

[ \begin{cases} , dp[i][0] = i, &\text{for } 0 \leq i \leq m, \ , dp[0][j] = j, &\text{for } 0 \leq j \leq n, \ , dp[i][j] = dp[i-1][j-1], &\text{if } initial[i-1] = target[j-1], \ , dp[i][j] = \min{ dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1] } + 1, &\text{if } initial[i-1] \neq target[j-1]. \end{cases} ]

Your program must read from standard input and output the result to standard output.

inputFormat

The input consists of two lines:

• The first line contains the initial string.
• The second line contains the target string.

The strings consist of printable characters and their lengths are at most 1000.

outputFormat

Output a single integer representing the minimum number of operations required to convert the initial string to the target string.

kitten
sitting

3