Minimum Edit Distance

Given two strings \( s_1 \) and \( s_2 \), your task is to compute the minimum number of operations required to transform \( s_1 \) into \( s_2 \). The allowed operations are:

• Insertion of a character,
• Deletion of a character,
• Substitution (replacement) of a character.

The problem is a classic example of computing the edit distance between two strings using dynamic programming. The final answer should be an integer representing the minimum number of operations needed for the transformation.

inputFormat

The input consists of two lines, where the first line contains the string \( s_1 \) and the second line contains the string \( s_2 \). Both strings can include any printable characters.

outputFormat

Output a single integer which is the minimum number of operations required to transform \( s_1 \) into \( s_2 \).

horse
ros

3