Levenshtein Distance Backtrack


Levenshtein distance between two strings is the minimum number of character edits(i.e. insertions, deletions or substitutions) required to change one string into the other.


Insertions: 0
Substitution: 0
Deletions: 0

When displaying search results, terms which are close enough to the queried string also need to be displayed. The terms which have lowest Levenshtein distance (similar in spelling) are shown before other terms in the list.

We calculate a m * n matrix and the number at the bottom-right corner is the levenshtein distance. Here m and n are the lengths of the first and second string respectively. To calculate the sequence of optimal operations required, one needs to traverse the matrix from the bottom-right corner to the top left corner (which has the value 0). Every vertical move is an insertion, left is deletion and a diagonal move is substitution.

The implementation above shows a backtrack done, which shows one of the paths possible, along with the number of operations. The calculation of the matrix is done using a javascript implentation on the algorithm and can be found here.