主题：计算编辑距离的Java示例代码

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"));
        }

 

}