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.
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.