Minimum Edit Distance

Given two strings s and t, find the minimum number of operations required to transform s into t. The allowed operations are insertion, deletion, and substitution. The problem can be solved using dynamic programming with the following recurrence:

\[ \text{dp}[i][j] = \begin{cases} i, & \text{if } j = 0 \\ j, & \text{if } i = 0 \\ \text{dp}[i-1][j-1], & \text{if } s_i = t_j \\ 1 + \min\begin{cases} \text{dp}[i-1][j] \\ \text{dp}[i][j-1] \\ \text{dp}[i-1][j-1] \end{cases}, & \text{if } s_i \neq t_j \end{cases} \]

where s_i and t_j denote the i-th and j-th characters of strings s and t respectively.

inputFormat

The input consists of two lines. The first line contains the string s and the second line contains the string t.

outputFormat

Output a single integer representing the minimum number of operations required to convert string s into string t.

kitten
sitting

3