In the second walkthrough video Brian uses two example words, "cat" and "ate" to demonstrate cost indexing of a tuple that lists the number of conversion steps and the last type of conversion made. For changing "ca" into "a", matrix position [2][1], he explains that once 'c' is changed into the empty string (1,D), we would substitute the second char in "ca" into the first char of "a". But since they are the same char, no substitution needs to be made. He then fills in the cost matrix with (1,S). Why would the last operation be S(substitution) when we aren't substituting anything? The only operation for this conversion is a deletion of 'c' to turn it into the empty string. Wouldn't we fill this matrix position with (1,D)?

1 Answer 1


The substitution still happens because the values of 'a' and 'a' are checked against each other but they don't need to be changed. that check being the last operation without additional cost equals (1, S).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .