Java中如何通过数组计算实现Levenshtein距离的简单矩阵？

本文共计692个文字，预计阅读时间需要3分钟。

相关专题

在 java 中用数组实现最短编辑距离（levenshtein distance），核心是构建一个二维 dp 数组 dp[i][j]，表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数（插入、删除、替换）。空间和逻辑都可控，适合理解算法本质。

初始化二维 DP 数组

设 word1 长度为 m，word2 长度为 n，申请 int[m+1][n+1] 数组：

• dp[0][j] = j：空字符串变 word2 前 j 字符，只能靠 j 次插入
• dp[i][0] = i：word1 前 i 字符变为空字符串，只能靠 i 次删除

填表逻辑：逐行逐列递推

对每个 i ∈ [1, m] 和 j ∈ [1, n]：

• 若 word1.charAt(i-1) == word2.charAt(j-1)，则 dp[i][j] = dp[i-1][j-1]（无需操作）
• 否则取三种操作的最小值加 1：
  • dp[i-1][j] + 1（删 word1[i-1]）
  • dp[i][j-1] + 1（在 word1 末尾插 word2[j-1]）
  • dp[i-1][j-1] + 1（将 word1[i-1] 替换为 word2[j-1]）

完整可运行示例代码

// 注意：索引从 0 开始，字符串下标需 -1

public static int levenshteinDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m + 1][n + 1]; <pre class="brush:php;toolbar:false;">// 初始化边界 for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; // 填充 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] + 1, // 删除 dp[i][j - 1] + 1), // 插入 dp[i - 1][j - 1] + 1 // 替换 ); } } } return dp[m][n];

}

立即学习“Java免费学习笔记（深入）”；

小技巧：空间优化到一维数组（可选）

因每行只依赖上一行，可用两个一维数组（prev 和 curr）或仅用一个数组滚动更新：

• 维护 int[] dp = new int[n + 1]
• 每次迭代前保存 dp[j-1]（即左上角值），用临时变量记录上一轮的 dp[j]
• 适合内存敏感场景，但初学建议先掌握二维写法