Edit Distance

The edit distance between two words (two sequences of alphanumeric characters) is defined as the minimum number of characters that need to be replaced, added, and/or deleted from the first word to transform it into the second word.

Your task in this problem is to find the edit distance between a given pair of words.

Examples

Consider the words “CAT” and “BAT”. The two words only differ in their first character. We only need to replace the “C” in “CAT” with a “B” to arrive at “BAT”. Therefore the edit distance is 1.

The words “FLY” and “FLYING” are identical in their first three characters, but the second word has three additional characters. Adding “ING” to the first word produces the second word. The edit distance in this case is 3.

Consider “GRAVE” and “GROOVY”. We can perform the following substitutions in the first word: (1) “A” ➝ “O”, (2) “E” ➝ “Y”, then (3) insert the character “O” in position 4 (after the first “O”). Thus, the edit distance in this case is 3.

Input Specification

The input will start with an integer N (N > 0) on a line by itself. This is followed by N lines, each of which contains a pair of words. Each word will be no longer than 255 characters, and will contain only non-space alphanumeric characters. The case of alphabetic characters is to be ignored.

Output Specification

For each pair of words, output the pair's sequence number (starting from 1 for the first pair) followed by “Edit Distance = ” and the value of the edit distance between the two words.

Sample Input

1. 5
2. Cat Bat
3. Fly Flying
4. Grave Groovy
5. Kitten Sitting
6. Alpha Omega

download as text file

Output for Sample Input

1. 1. Edit Distance = 1
2. 2. Edit Distance = 3
3. 3. Edit Distance = 3
4. 4. Edit Distance = 3
5. 5. Edit Distance = 4

download as text file