Minimum Operations to Transform Strings

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\). The allowed operations are:

• Insertion of a character
• Deletion of a character
• Replacement of a character

The answer is the minimum number of these operations required to transform \(S\) into \(T\). This is a classic Edit Distance problem, where the recurrence relation is given by

[ \text{dp}[i][j]= \begin{cases} i & \text{if } j=0,\ j & \text{if } i=0,\ \text{dp}[i-1][j-1] & \text{if } S_i = T_j,\ \min(\text{dp}[i-1][j],, \text{dp}[i][j-1],, \text{dp}[i-1][j-1]) + 1 & \text{if } S_i \neq T_j. \end{cases} ]

Good luck!

inputFormat

The input consists of two lines. The first line contains the original string \(S\) and the second line contains the target string \(T\).

outputFormat

Output a single integer representing the minimum number of operations needed to transform string \(S\) into string \(T\).

kitten
sitting

3