public class exec
{

        //****************************
        // Get minimum of three values
        //****************************

        private static int Minimum(int a, int b, int c)
        {
                int mi;

                mi = a;
                if (b < mi)
                {
                        mi = b;
                }
                if (c < mi)
                {
                        mi = c;
                }
                return mi;

        }

        //*****************************
        // Compute Levenshtein distance
        //*****************************

        public static int LD(String s, String t)
        {
                int d[][]; // matrix
                int n; // length of s
                int m; // length of t
                int i; // iterates through s
                int j; // iterates through t
                char s_i; // ith character of s
                char t_j; // jth character of t
                int cost; // cost

                // Step 1

                n = s.length();
                m = t.length();
                if (n == 0)
                {
                        return m;
                }
                if (m == 0)
                {
                        return n;
                }
                d = new int[n + 1][m + 1];

                // Step 2

                for (i = 0; i <= n; i++)
                {
                        d[0] = i;
                }

                for (j = 0; j <= m; j++)
                {
                        d[0][j] = j;
                }

                // Step 3

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

                        s_i = s.charAt(i - 1);

                        // Step 4

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

                                t_j = t.charAt(j - 1);

                                // Step 5

                                if (s_i == t_j)
                                {
                                        cost = 0;
                                }
                                else
                                {
                                        cost = 1;
                                }

                                // Step 6

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

                        }

                }

                // Step 7

                return d[n][m];

        }
       
        public static void main(String [] args)
        {
                System.out.println(LD("cat","dog"));
        }

}