MARCIN.com

The Levenshtein distance is used to measure a difference between two strings, which is interpreted as the number of insertions, deletions and substitutions required to transform the source string into the target one. For example, if you want to change word Marcin into Martine, you need to substitute c with t and add e at the end, so the Levenshtein distance is equal to 2.

The implementation can use an auxiliary two-dimensional array. Its each element (with i and j indices) stores a distance between the i first characters of the input string to the j first characters of the target string. The code is presented below:

int levenshtein(string x, string y)
{
    int[,] t = new int[x.Length + 1, y.Length + 1];

    // Convert i-length input string to empty string, by removing all chars.
    for (int i = 0; i <= x.Length; i++) { t[i, 0] = i; }

    // Convert empty string to j-length target string, by adding j chars.
    for (int j = 1; j <= y.Length; j++) { t[0, j] = j; }
    
    // Calculate distances between i first chars of input string
    // and the j first chars of target string.
    for (int i = 1; i <= x.Length; i++)
    {
        for (int j = 1; j <= y.Length; j++)
        {
            int deletion = t[i - 1, j] + 1;
            int insertion = t[i, j - 1] + 1;
            int replaceCost = x[i - 1] != y[j - 1] ? 1 : 0;
            int replace = t[i - 1, j - 1] + replaceCost;
            t[i, j] = Math.Min(Math.Min(deletion, insertion), replace);
        }
    }

    return t[x.Length, y.Length];
}

You can check this code by the following lines:

int distance = levenshtein("marcin", "martine");
Console.WriteLine($"Distance is equal to {distance}.");

The result is shown as follows:

Distance is equal to 2.

The content, including any part of code, is presented without warranty, either express or implied. The author cannot be held liable for any damages caused or alleged to have been caused directly or indirectly by any content shown on this website.