Minimum Edit Distance

Given two strings \(s_1\) and \(s_2\), compute the minimum number of operations required to transform \(s_1\) into \(s_2\). The permitted operations are insertion, deletion, and substitution, each with a cost of 1. This problem is equivalent to calculating the edit distance between the two strings using a dynamic programming approach.

Note: The edit distance is defined as the minimum number of operations (insertions, deletions, and substitutions) needed to convert one string into another. The recurrence relation can be written as:

\[ \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_1[i-1] = s_2[j-1], \\ 1 + \min\{\text{dp}[i-1][j],\, \text{dp}[i][j-1],\, \text{dp}[i-1][j-1]\} & \text{if } s_1[i-1] \neq s_2[j-1]. \end{cases} \]

Input and output are handled through standard input and standard output respectively.

inputFormat

The input begins with an integer \(T\) on the first line, representing the number of test cases.

Each test case consists of two lines:

• The first line contains the string \(s_1\).
• The second line contains the string \(s_2\).

Strings may be empty.

outputFormat

For each test case, output a single integer on a new line representing the minimum edit distance between \(s_1\) and \(s_2\).

3
horse
ros
intention
execution
abc
abc

3
5
0