编辑距离

参考文章 https://www.jianshu.com/p/8e0204dbb765

编辑距离是针对两个字符串的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。
莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
俄罗斯科学家弗拉基米尔·莱文斯坦在1965年提出这个概念。

算法实现：动态规划。动态规划通常基于一个递推公式及一个或多个初始状态，将当前子问题的解由上一子问题的解推出。

Java实现

import java.util.Scanner;

public class LevenshteinDistance {
    /**
     * 从3个数中选出最小值
     */
    private static int minOfTreeNum(int a, int b, int c) {
        int minNum = a;
        if (minNum > b) {
            minNum = b;
        }
        if (minNum > c) {
            minNum = c;
        }
        return minNum;
    }

    public static void main(String[] args) {
        String x = new Scanner(System.in).nextLine();
        String y = new Scanner(System.in).nextLine();
        // 声明一个二维数组存放编辑距离
        int[][] levenST = new int[x.length() + 1][y.length() + 1];
        // 初始化二维数组，即写入最简单情形的levenshtein距离
        for (int i = 0; i <= x.length(); i++) {
            levenST[i][0] = i;
        }
        for (int j = 0; j <= y.length(); j++) {
            levenST[0][j] = j;
        }
        // 将字符串x与y中的字母两两比较，得到相应字符串的编辑距离
        for (int i = 1; i <= x.length(); i++) {
            for (int j = 1; j <= y.length(); j++) {
                levenST[i][j] = minOfTreeNum(levenST[i - 1][j] + 1, levenST[i][j - 1] + 1, levenST[i - 1][j - 1] + (x.charAt(i - 1) != y.charAt(j - 1) ? 1 : 0));
            }
        }
        System.out.println("Levenshtein Distance: " + levenST[x.length()][y.length()]);
    }
}