Edit Distance

You are given two strings. Your task is to compute the minimum number of operations required to convert the first string to the second string. The operations allowed are:

• Insertion of a single character.
• Deletion of a single character.
• Replacement of one character with another.

This is a classic dynamic programming problem. The recurrence relation governing the state transition is given by: \[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] & \text{if } s_i = t_j, \\ \min(\text{dp}[i-1][j] + 1,\; \text{dp}[i][j-1] + 1,\; \text{dp}[i-1][j-1] + 1) & \text{if } s_i \neq t_j. \end{cases} \] where \(s_i\) and \(t_j\) denote the characters at position \(i\) and \(j\) in the first and second string respectively.

inputFormat

The input is read from standard input (stdin). It consists of two lines. The first line contains the first string, and the second line contains the second string.

outputFormat

Print to standard output (stdout) a single integer representing the minimum number of operations required to convert the first string into the second string.## sample

kitten
sitting

3