Edit Distance Transformation

Given two strings, \(s\) and \(t\), determine the minimum number of operations required to transform \(s\) into \(t\). The allowed operations are insertion, deletion, or substitution of a single character. This classic problem, also known as the edit distance problem, is widely used in text correction and computational biology.

Formally, let \(dp[i][j]\) denote the minimum number of operations required to transform the first \(i\) characters of \(s\) into the first \(j\) characters of \(t\). The recurrence is given by:

\(dp[i][j]=\begin{cases}dp[i-1][j-1]&\text{if } s[i-1]=t[j-1]\\1+\min(dp[i-1][j],\;dp[i][j-1],\;dp[i-1][j-1])&\text{otherwise}\end{cases}\)

inputFormat

The input consists of two lines read from standard input (stdin). The first line contains the string (s) and the second line contains the string (t). Both strings can be empty.

outputFormat

Output a single integer to standard output (stdout) that represents the minimum number of operations required to transform (s) into (t).## sample

kitten
sitting

3