Moving Left to Right: Starting with Column "B"

To understand how to fill in the matrix, let's begin with the column corresponding to the letter B from the string best. Our goal is to move left to right and populate each cell with the least "costly" way to transform the strings up to that point.

The Three Choices for Each Cell

Remember our guidelines for each cell:

1. From Above: The cell immediately above plus 1.
2. From the Left: The cell immediately to the left plus 1.
3. From the Diagonal: The cell diagonally above and to the left, plus the cost (0 if the letters are the same, and 1 otherwise).

Filling In the "B" Column

Starting at the * in the prior table, we see that B and T are different. So, the edit cost is 1. With this in mind, we have three calculations:

1. From Above: (1 + 1 = 2)
2. From the Left: (1 + 1 = 2)
3. From the Diagonal: (0 + 1 = 1)

The minimum of these is 1, so we place it in the cell where B intersects with T.

Here's how our matrix looks after filling in the "B" column:

We've successfully filled in the first column for the letter B. We'd continue this process for each of the remaining columns to complete the matrix and find the total edit distance.