Heuristic String Comparison with Levenshtein Distance
The Levenshtein Distance algorithm provides a practical example of dynamic programming. It allows us to determine the minimum number of operations required to transform one string into another using the operations: Add, Delete, Alter, or Keep. Compare strings "kitten" and "sitting" s i t t i n g 0 1 2 3 4 5 6 7 k 1 1 2 3 4 5 6 7 i 2 2 1 2 3 4 5 6 t 3 3 2 1 2 3 4 5 t 4 4 3 2 1 2 3 4 e 5 5 4 3 2 2 3 4 n 6 6 5 4 3 3 2 3 In the top row we have how many operations it would take to change the substring (up to the column) to a null string. This would require a delete for every character of the source string. Therefore the top row is the count of the characters in the source string and the horizontal move across the matrix r...