动态规划之编辑距离（java实现）_java实现动态规划法计算最短编辑距离

动态规划之编辑距离

private static int minimum(int a,int b,int c)
        {
            return Math.min(Math.min(a,b),c);
        }

        public static int computeLevenshteinDistance(CharSequence src,CharSequence dst)
        {
            int [][] distance = new int[src.length()+1][dst.length()+1];

            for (int i=0;i<=src.length();i++)
                distance[i][0]=i;
            for(int j=0;j<dst.length();j++)
                distance[0][j]=j;
            for(int i=1;i<=src.length();i++)
            {
                for(int j=1;j<=dst.length();j++)
                {
                    int flag = (src.charAt(i - 1) == dst.charAt(j - 1)) ? 0 : 1;
                    distance[i][j] = minimum(distance[i - 1][j] + 1, distance[i][j - 1] + 1, distance[i - 1][j - 1] + flag);
                }

            }
            return distance[src.length()][dst.length()];
        }
        public static void main(String[] args)
        {
            String s1="ABcCER";
            String s2="CDvRC";

             System.out.println("最短编辑距离为 "+computeLevenshteinDistance(s1,s2));
        }


    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

附运行结果