Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple Lavenstein edit distance algorithm
public class Program
{
public void Main()
{
PrintEditDistance("ab", "ab");
PrintEditDistance("bbc", "abc");
PrintEditDistance("bbbc", "bbc");
PrintEditDistance("xyza", "abcx");
}
public void PrintEditDistance(string s1, string s2)
{
Console.WriteLine($"{Lavenstein.GetEditDistance(s1, s2)} : {s1} : {s2}");
}
public class Lavenstein
{
public static int GetEditDistance(string s1, string s2)
{
var costsTable = new int[s1.Length, s2.Length];
for(var i = 0; i < s1.Length; i++)
{
for(var j = 0; j < s2.Length; j++)
{
var char1 = s1[i];
var char2 = s2[j];
var cost = char1 == char2 ? 0 : 1;
if(i == 0 && j == 0)
{
costsTable[i, j] = cost;
}
else
{
var toMinCost = new List<int>();
if (i - 1 > -1 && j - 1 > -1)
toMinCost.Add(cost + costsTable[i-1, j-1]);
if (i - 1 > -1)
toMinCost.Add(1 + costsTable[i-1, j]);
if (j - 1 > -1)
toMinCost.Add(1 + costsTable[i, j-1]);
costsTable[i, j] = toMinCost.Min();
}
}
}
return costsTable[s1.Length -1, s2.Length -1];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment