编辑距离的java代码

编辑距离（Edit Distance），也称为Levenshtein距离，是用来比较两个字符串之间的相似度的方法。它可以通过一系列的编辑操作将一个字符串转换为另一个字符串，包括插入、删除和替换等操作。

以下是一个Java代码示例，用于计算两个字符串之间的编辑距离：

public class EditDistance {

    public static int editDistance(String word1, String word2) {

        int m = word1.length();

        int n = word2.length();

        // 初始化距离矩阵

        int[][] dp = new int[m + 1][n + 1];

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

            dp[i][0] = i;

        }

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

            dp[0][j] = j;

        }

        // 计算距离矩阵

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

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

                int cost = (word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1;

                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);

            }

        }

        return dp[m][n];

    }

    public static void main(String[] args) {

        String word1 = "kitten";

        String word2 = "sitting";

        System.out.println("编辑距离为：" + editDistance(word1, word2));

    }

}

这个示例代码中的 editDistance() 方法接收两个字符串作为参数，计算并返回它们之间的编辑距离。该方法使用动态规划算法实现，时间复杂度为 O(mn)，其中 m 和 n 分别是两个字符串的长度。在这个示例中，我们计算了单词"kitten"和"sitting"之间的编辑距离。