Algorithms For Dummies

  Relying on Dynamic Programming 

     319

between each letter in the rows compared to those in the columns. In this way, the 

algorithm makes a number of comparisons equivalent to the multiplication of the 

number of the letters in the two strings. As the algorithm continues, it accounts 

for the result of previous comparisons by looking at the solutions present in the 

previous matrix cells and choosing the solution with the least number of edits.

When the matrix iteration completes, the resulting number represents the mini-

mum number of edits necessary for the transformation to occur — the smaller the 

number, the more similar the two strings. Retracing from the last cell to the first 

one by moving to the previous cell with the least value (if more directions are 

available, it prefers to move diagonally) hints at what transformations to execute 

(see Figure 16-3):