Solution: The Edit Distance Problem

using System;
class Program
{
    /// <summary>
    /// Calculates the minimum Levenshtein distance between two strings.
    /// </summary>
    /// <param name="str1">First string.</param>
    /// <param name="str2">Second string.</param>
    /// <param name="m">Length of the first string.</param>
    /// <param name="n">Length of the second string.</param>
    /// <returns>The minimum number of Levenshtein distance operations required to transform the first string into the second.</returns>
    public static int MinEditDistRecursive(string str1, string str2, int m, int n)
    {
        // If first string is empty, the only option is to
        // insert all characters of second string into first
        if (m == 0)
            return n;
        // If second string is empty, the only option is to
        // remove all characters of first string
        if (n == 0)
            return m;
        // If last characters of two strings are the same, ignore last characters
        // and get count for remaining strings
        if (str1[m - 1] == str2[n - 1])
            return MinEditDistRecursive(str1, str2, m - 1, n - 1);
        // If last characters are not the same, consider all three operations
        // on the last character of the first string, recursively compute minimum
        // cost for all three operations and take minimum of the three values
        int insertOp = MinEditDistRecursive(str1, str2, m, n - 1);     // Insert
        int removeOp = MinEditDistRecursive(str1, str2, m - 1, n);     // Remove
        int replaceOp = MinEditDistRecursive(str1, str2, m - 1, n - 1); // Replace
        return 1 + Math.Min(Math.Min(insertOp, removeOp), replaceOp);
    }
    /// <summary>
    /// Calculates the minimum Levenshtein distance between two strings.
    /// </summary>
    /// <param name="str1">First string.</param>
    /// <param name="str2">Second string.</param>
    /// <returns>The minimum number of Levenshtein distance operations required to transform the first string into the second.</returns>
    public static int MinEditDist(string str1, string str2)
    {
        return MinEditDistRecursive(str1, str2, str1.Length, str2.Length);
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        string str1 = "sunday";
        string str2 = "saturday";
        Console.WriteLine(MinEditDist(str1, str2));
    }
}