Minimum Edit Distance

You are given two strings and your task is to compute the minimum number of single-character edits (insertions, deletions, or substitutions) needed to transform the first string into the second string.

Formally, given two strings \( s_1 \) and \( s_2 \), you need to determine the smallest number of operations required so that \( s_1 \) becomes identical to \( s_2 \). The solution is expected to be implemented using dynamic programming.

Example:

• For s1 = "kitten" and s2 = "sitting", the answer is 3.
• For s1 = "flaw" and s2 = "lawn", the answer is 2.
• For s1 = "intention" and s2 = "execution", the answer is 5.

inputFormat

The input consists of exactly two lines.

• The first line contains the first string \( s_1 \).
• The second line contains the second string \( s_2 \).

Both strings can be empty.

outputFormat

Output a single integer representing the minimum number of edit operations required to transform the first string into the second string.

kitten
sitting

3