Minimum Edit Distance

In this problem, you are given two strings s1 and s2. Your task is to compute the minimum number of operations required to convert s1 into s2. The allowed operations are insertion, deletion, and substitution of a single character.

You can solve this problem using dynamic programming. The recurrence relation is given by:

$$ \textbf{dp}[i][j] = \begin{cases} j & \text{if } i = 0,\\ i & \text{if } j = 0,\\ \textbf{dp}[i-1][j-1] & \text{if } s1_{i-1} = s2_{j-1},\\ 1 + \min\{\textbf{dp}[i-1][j],\, \textbf{dp}[i][j-1],\, \textbf{dp}[i-1][j-1]\} & \text{otherwise.} \end{cases} $$

The final answer is dp[m][n] where m and n are the lengths of s1 and s2 respectively. This problem is a classic example of the edit distance problem.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains the string s1 and the second line contains the string s2 (which may be empty).

outputFormat

Output via standard output (stdout) a single integer representing the minimum number of operations required to convert s1 into s2.

kitten
sitting

3