Levenshtein Distance

This problem requires you to compute the Levenshtein distance between two given strings. The Levenshtein distance between two strings is the minimum number of single-character edits (insertions, deletions, or substitutions) needed to change one string into the other.

You are expected to implement a solution using dynamic programming. The recurrence relation used in the solution is given by:

\[ \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] + \begin{cases} 0, & \text{if } s1[i-1] = s2[j-1] \\ 1, & \text{otherwise} \end{cases} \end{cases} \]

where dp[i][j] represents the minimum number of operations required to convert the first i characters of s1 into the first j characters of s2.

inputFormat

The input consists of two lines. The first line contains the string s1 and the second line contains the string s2. Both strings consist of printable characters.

outputFormat

Output a single integer indicating the Levenshtein distance between the two strings.

kitten
sitting

3