using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine(Distance("abcydef", "abxidef"));

    }

    public static int Distance(string s1, string s2) {

        return DistanceDynamic(s1, s2, s1.Length, s2.Length);

    }

​

    /*

    public static int DistanceRecursive(string s1, string s2, int m, int n) {

        if (m == 0)

            return n;

        if (n == 0)

            return m;

        if (s1[m - 1] == s2[n - 1])

            return DistanceRecursive(s1, s2, m, n);

        return 1 + Math.Min(Math.Min(DistanceRecursive(s1, s2, m - 1, n), DistanceRecursive(s1, s2, m, n - 1)), DistanceRecursive(s1, s2, m - 1, n - 1));

    }

    */

    public static int DistanceDynamic(string s1, string s2, int m, int n) {

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

        for (int i = 0; i <= m; i++) {

            for (int j = 0; j <= n; j++) {

                if (i == 0)

                    dist[i, j] = j;

                else if (j == 0)

                    dist[i, j] = i;

                else if (s1[i - 1] == s2[j - 1])

                    dist[i, j] = dist [i - 1, j - 1];

                else

                    dist[i, j] = 1 + Math.Min(Math.Min(dist[i - 1, j], dist[i, j - 1]), dist[i - 1, j - 1]);

            }

        }

        return dist[m, n];

    }

}