# Levenshtein distance (Edit distance)

The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of:

1. replace a letter,
2. insert a letter, or
3. delete a letter

void Main()
{

}

class EditDistanceAlgo
{
static int[,] m;
public static char diagCh;
public static int LevenshteinDistance(string first, string second)
{
int[,] map = new int[first.Length + 1, second.Length + 1];
for (int i = 0; i <= first.Length; i++)
map[i, 0] = i;
for (int j = 0; j <= second.Length; j++)
map[0, j] = j;
for (int j = 1; j <= second.Length; j++)
for (int i = 1; i <= first.Length; i++)
if (first[i - 1] == second[j - 1])
map[i, j] = map[i - 1, j - 1];  //no operation
else
map[i, j] = Math.Min(Math.Min(
map[i - 1, j] + 1,    //a deletion
map[i, j - 1] + 1),   //an insertion
map[i - 1, j - 1] + 1 //a substitution
);
TraceBack("", "", "", map, first.Length, second.Length, first, second);
return map[first.Length, second.Length];
}
public static void TraceBack(string row1, string row2, string row3, int[,] mm, int i, int j, string s1, string s2)
{
string result = "";
if (i > 0 && j > 0)
{
var diag = mm[i - 1, j - 1];
diagCh = '|';
if (s1[i - 1] != s2[j - 1])
{
diag++; diagCh = ' ';
}
if (mm[i, j] == diag)
TraceBack(s1[i - 1] + row1, diagCh + row2, s2[j - 1] + row3, mm, i - 1, j - 1, s1, s2);    // change or match
else if (mm[i, j] == mm[i - 1, j] - 0 + 1) // delete
TraceBack(s1[i - 1] + row1, ' ' + row2, '-' + row3, mm, i - 1, j, s1, s2);
else
TraceBack('-' + row1, ' ' + row2, s2[j - 1] + row3, mm, i, j - 1, s1, s2);      // insertion
}
else if (i > 0)
TraceBack(s1[i - 1] + row1, ' ' + row2, '-' + row3, mm, i - 1, j, s1, s2);
else if (j > 0)
TraceBack('-' + row1, ' ' + row2, s2[j - 1] + row3, mm, i, j - 1, s1, s2);
else // i==0 and j==0
result += row1 + '\n' + row2 + '\n' + row3 + '\n';
Console.WriteLine(result);
}//traceBack
}

Reactions