Levenshtein distance

Needed to determine the distance between 2 strings.

Here is a basic implementation of the “Levenshtein distance” algorithm, which measures the distance as the number of edits required to change one string to the other via a series of insertion, deletion and substitution operations.

The following implementation is based of the pseudo-code on wikipedia. (http://en.wikipedia.org/wiki/Levenshtein_distance)

public class StringEditDistance 
{
    //http://en.wikipedia.org/wiki/Levenshtein_distance
    public int LevenshteinDistance (string s, string t) 
    {
        int m = s.Length; //length of s
        int n = t.Length; //length of t
        
        if(n == 0) return m;
        if(m == 0) return n;
        
        int[,] d = new int[m+1, n+1]; // d is a table with m+1 rows and n+1 columns
        for(int i = 0; i <= m; i++)
            d[i, 0] = i; //deletion
        for(int j = 0; j <= n; j++)
            d[0, j] = j; //insertion
        
        for(int j = 1; j <= n; j++) 
        {
            for(int i = 1; i <= m; i++) 
            {
                if (s.Substring(i-1, 1) == t.Substring(j-1, 1))
                {
                    d[i,j] = d[i-1,j-1];
                }
                else
                {
                    int deletion = d[i - 1, j] + 1;
                    int insertion = d[i, j - 1] + 1;
                    int substitution = d[i - 1, j - 1] + 1;
                    d[i, j] = Math.Min(Math.Min(deletion, insertion),substitution);
                }
            }
        }
        return d[m, n];
    }
}