In the case of string editing and distance we will construct eight by nine grid and

our goal is to compute all edit distances D(i, j)

corresponding to all nodes in this grid.

For example, for i and j equal to four and four.

How will we compute the corresponding distance D(i, j)?

Let's start by filling distances D(i, 0) in the first column of this matrix.

It is easy because indeed we are comparing an i-prefix

of string A against a 0-prefix of string D and

therefore this edit distance for i-prefix will be equal to i.

That's what's shown here, similarly we can easily fill the first row in this matrix.

And now let's try to compute what will be the distance D(1,1)

corresponding to comparison of string consisting of single symbol E,

with a string consisting of single symbol D,

there are three possible ways to arrive to the node (1, 1):

from the nodes (0, 0), (0, 1), and (1, 0).

Which one should be the way we will select to find the optimal edit distance.

According to the previous recurrency, we should select

the one of three directions that gives minimal value for

D(i, j), which is minimum of 2, 2, and 1 and

therefore we arrive to node (1, 1) by diagonal edge.

Let's keep this in memory that

the right direction to arrive at node (1, 1) was the diagonal direction.