## Difference between two strings – Levenshtein Algorithm

So now after a long time, I am going to write about an algorithm which I recently read, and found it very useful.

This algorithm is about, how different two strings are, and how many minimum operations are required to convert smaller string in length to larger (if their lengths are different). If the two string are of equal length then the number of charcaters that differ in two strings is the difference of strings. For example, in ‘computer’ and ‘computes’ the difference is 1 and in ‘test’ and ‘goat’ the difference is 3. Such distance is called as Hamming distance or edit distance simply put.

However if the strings are different in length then we use Levenshtein Algorithm or edit distance. Which works as follows.

For the two strings s1(cat) and s2(cots) of lengths m(3) and n(4), make an array of n*m and fill the each cell in 0th row with it’s corresponding column number and each cell in 0th column with it’s corresponding row number so our array ‘D’ will look like,

0 1 2 3

1

2

3

4

After this we compute a value in ‘temp’ which is 0 if s1[i] = s1[j] and 1 otherwise. And then find the minimum of D[i-1][j] + 1, D[i][j-1] +1 and D[i-1][j-1] + cost and assign it to D[i][j], where ‘i’ and ‘j’ are indeces while we compute. When we fill this array the last value in D[n][m] will give you the minimum number of moves required to convert str1(smaller) into str2(larger).

Here D[i-1][j] + 1, tell us if it is selected that we have to insert value in str1, if we select D[i][j-1] + 1 then we have to delete from str2 and if D[i-1][j-1] + cost is selected then we have to substitue in str1.

This is an interesting algorithm to try and then code, and is useful to find closest matches for a string and then can be used in many applications.

most basic (101) dynamic programming algorithm ever

very interesting, but I don’t agree with you

Idetrorce

U’ve got good pics, the site could use a tiny bit of work (no offense) its still awesome