Minimum Operations to Convert String

You are given two strings \(S\) and \(T\). Your task is to determine the minimum number of operations required to convert string \(S\) into string \(T\). You are allowed to perform the following three operations:

• Insertion: Insert a single character at any position.
• Deletion: Delete a single character from the string.
• Replacement: Replace one character with another.

The problem is a classic "Edit Distance" problem and can be solved using dynamic programming.

For example, given \(S = \texttt{horse}\) and \(T = \texttt{ros}\), the minimum number of operations required is 3.

inputFormat

The input consists of exactly two lines:

1. The first line contains the string \(S\). It may be empty.
2. The second line contains the string \(T\). It may also be empty.

Both strings consist of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of operations (insertions, deletions, or replacements) required to convert \(S\) to \(T\).

horse
ros

3