Building the Edit Distance Matrix: A Concrete Example

Let's dive into another example and step through the entire thing.

The Core Idea: Cumulative Transformation Distance

To find the smallest number of transformations needed, we will fill in a matrix while keeping track of the cumulative transformation distance. This is the running total of changes needed to make the strings match up to that point.

Here's how we fill in each cell of the matrix:

1. From Above: Take the value from the cell immediately above and add 1: $d[i-1,j]+1$
2. From the Left: Take the value from the cell immediately to the left and add 1: $d[i,j-1]+1$
3. From the Diagonal: Take the value from the cell diagonally above and to the left, and add the cost: $d[i-1,j-1]+\text{cost}$

Step-by-Step Matrix Building: The Example of best vs test

Let's make this real by constructing the matrix for the strings best and test. First, we initialize a row and a column based on the lengths of our two strings:

Now let's fill it in, guided by our three rules:

1. From Above: If we just want to insert a letter, we look at the cell above and add 1.
2. From the Left: If we want to delete a letter, we look at the cell to the left and add 1.
3. From the Diagonal: If we want to substitute a letter, we look diagonally and add the cost (which is 0 if the letters are the same, and 1 otherwise).