Minimum Edit Distance

Given two strings s1 and s2, your task is to compute the minimum number of operations required to transform s1 into s2. The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Substitution of a single character

You can refer to the formula in \( \text{dp}[i][j] = \min\big\{ \text{dp}[i-1][j] + 1,\, \text{dp}[i][j-1] + 1,\, \text{dp}[i-1][j-1] + \delta \big\} \), where \( \delta = 0 \) if the characters are equal and \( 1 \) otherwise. The answer is stored in \( \text{dp}[m][n] \), where \( m \) and \( n \) are the lengths of s1 and s2 respectively.

Input/Output Format: The input consists of two lines, each containing one string. The output is a single integer representing the minimum number of operations needed.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains the string s1.
• The second line contains the string s2.

outputFormat

Output a single integer to standard output (stdout) which is the minimum number of operations required to transform s1 into s2.

kitten
sitting

3