Minimum Edit Distance

You are given two strings, S and T. Your task is to compute the minimum number of operations required to transform S into T. You are allowed to perform three types of operations:

• Insertion
• Deletion
• Substitution

This problem can be solved using dynamic programming. The transition relation is based on comparing the last characters of the current substrings of S and T. If they match, no new operation is needed; otherwise, choose the minimum among insertion, deletion, and substitution operations. The mathematical formulation using LaTeX is as follows:

\[ \text{dp}[i][j] = \begin{cases} j & \text{if } i = 0, \\ i & \text{if } j = 0, \\ \text{dp}[i-1][j-1] & \text{if } S[i-1] = T[j-1], \\ 1 + \min\{\text{dp}[i][j-1],\; \text{dp}[i-1][j],\; \text{dp}[i-1][j-1]\} & \text{otherwise.} \end{cases} \]

Implement a solution that reads the two strings from standard input and outputs the minimum number of operations to transform S into T.

inputFormat

The input consists of two lines:

1. The first line contains the string S.
2. The second line contains the string T.

Both strings may be empty and consist of lowercase letters.

outputFormat

Output a single integer representing the minimum number of operations required to convert string S into string T.

kitten
sitting

3