Java实现编辑距离（动态规划详解：从零开始掌握字符串相似度计算）

为什么用动态规划？

暴力递归会重复计算大量子问题，效率极低。而动态规划算法通过构建一个二维表格，自底向上地保存中间结果，避免重复计算，时间复杂度为 O(m×n)，其中 m 和 n 分别是两个字符串的长度。

Java实现步骤详解

我们以字符串 "kitten" 和 "sitting" 为例，目标是计算它们之间的编辑距离。

1. 创建DP表

创建一个 (m+1) × (n+1) 的二维数组 dp，其中 dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数。

2. 初始化边界

- dp[0][j] = j：空字符串变成 word2 的前 j 个字符，需要 j 次插入
- dp[i][0] = i：word1 的前 i 个字符变成空字符串，需要 i 次删除

3. 状态转移方程

对于每个位置 (i, j)：

• 如果 word1.charAt(i-1) == word2.charAt(j-1)，则 dp[i][j] = dp[i-1][j-1]（无需操作）
• 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  其中：
    • dp[i-1][j] + 1：删除
    • dp[i][j-1] + 1：插入
    • dp[i-1][j-1] + 1：替换

完整Java代码实现

public class EditDistance {        public static int minDistance(String word1, String word2) {        int m = word1.length();        int n = word2.length();                // 创建 (m+1) x (n+1) 的DP表        int[][] dp = new int[m + 1][n + 1];                // 初始化第一行：空字符串转为word2的前j个字符        for (int j = 0; j <= n; j++) {            dp[0][j] = j;        }                // 初始化第一列：word1的前i个字符转为空字符串        for (int i = 0; i <= m; i++) {            dp[i][0] = i;        }                // 填充DP表        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1];                } else {                    dp[i][j] = Math.min(                        Math.min(dp[i - 1][j], dp[i][j - 1]),                        dp[i - 1][j - 1]                    ) + 1;                }            }        }                return dp[m][n];    }        public static void main(String[] args) {        String str1 = "kitten";        String str2 = "sitting";        System.out.println("编辑距离: " + minDistance(str1, str2)); // 输出: 3    }}

运行结果与解释

对于 "kitten" → "sitting"，编辑距离为 3，操作步骤如下：

1. k → s（替换）
2. e → i（替换）
3. 末尾插入 g

总结

通过本教程，你已经掌握了如何使用Java编辑距离算法来计算两个字符串的字符串相似度。这种基于动态规划算法的方法高效且易于理解，是解决此类问题的经典方案。无论是面试准备还是实际项目开发，Levenshtein距离都是一个非常实用的工具。

小提示：你可以尝试优化空间复杂度，将二维DP表压缩为一维数组，进一步提升性能！