Edit Distance

Given two strings, your task is to compute the minimum number of operations required to convert the first string into the second string. The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Substitution of a single character

This problem is a classic example of a dynamic programming problem, often referred to as the Edit Distance or Levenshtein Distance problem.

You are required to read the input from stdin and print the result to stdout.

Note: If one or both of the input strings are empty, consider them as empty strings.

inputFormat

The input consists of exactly two lines. The first line contains the first string word1, and the second line contains the second string word2. Both strings may be empty.

outputFormat

Print a single integer representing the minimum number of operations required to convert word1 to word2.

horse
ros

3