using System;

public class Program

{

    public static void Main()

    {

        //Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant"));

        //Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha"));

        //Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax"));

        Console.WriteLine(LevenshteinDistance.Compute("221 James Street", "221 James St."));

    }

}

​

/// <summary>

/// Contains approximate string matching

/// </summary>

static class LevenshteinDistance

{

    /// <summary>

    /// Compute the distance between two strings.

    /// </summary>

    public static int Compute(string s, string t)

    {

    int n = s.Length;

    int m = t.Length;

    int[,] d = new int[n + 1, m + 1];

​

    // Step 1

    if (n == 0)

    {

        return m;

    }

​

    if (m == 0)

    {

        return n;

    }

​

    // Step 2

    for (int i = 0; i <= n; d[i, 0] = i++)

    {

    }

​

    for (int j = 0; j <= m; d[0, j] = j++)

    {

    }

​

    // Step 3

    for (int i = 1; i <= n; i++)

    {

        //Step 4

        for (int j = 1; j <= m; j++)

        {

        // Step 5

        int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

​

        // Step 6

        d[i, j] = Math.Min(

            Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),

            d[i - 1, j - 1] + cost);

        }

    }

    // Step 7

    return d[n, m];

    }

}

​

​