Minimum Edit Distance

Given two strings S and T, transform S into T using the following operations:

• Insertion of a character.
• Deletion of a character.
• Replacement of a character.

Your task is to compute the minimum number of operations needed to convert S into T.

The dynamic programming recurrence can be written in \( \LaTeX \) as follows:

\[ \text{dp}(i,j)=\min\begin{cases} \text{dp}(i-1,j)+1,\\ \text{dp}(i,j-1)+1,\\ \text{dp}(i-1,j-1)+\delta(s_i,t_j)\\ \end{cases} \]

where \( \delta(s_i,t_j)=0 \) if \( s_i=t_j \) and \( 1 \) otherwise.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains the string S and the second line contains the string T.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of edit operations required to transform S into T.## sample

kitten
sitting

3