Java中计算编辑距离最常用动态规划，时间复杂度O(m×n)，空间可优化至O(min(m,n))；核心是dpi表示word1前i字符转word2前j字符的最少操作数，递推式依据字符是否相等分两种情况。
Java 中计算两个字符串的编辑距离（Levenshtein Distance），最常用的是动态规划实现，时间复杂度 O(m×n)，空间可优化到 O(min(m,n))。
核心思路：构建二维 DP 表
定义 dp[i][j] 表示将 word1 的前 i 个字符 转换为 word2 的前 j 个字符 所需的最少编辑操作数（插入、删除、替换）。 递推关系如下：
- 若 word1.charAt(i-1) == word2.charAt(j-1)，则 dp[i][j] = dp[i-1][j-1]（无需操作）
- 否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
• dp[i-1][j] → 删除 word1 第 i 个字符
• dp[i][j-1] → 在 word1 末尾插入 word2 第 j 个字符
• dp[i-1][j-1] → 替换 word1 第 i 个字符为 word2 第 j 个字符
基础实现（二维数组）
适合理解逻辑，代码清晰：
public static int levenshteinDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
<pre class="brush:php;toolbar:false;">// 初始化边界：转成空串需删光
for (int i = 0; i <p>}</p>空间优化版（一维数组）
因每行只依赖上一行，可用两个一维数组或滚动数组。更进一步，仅用一个长度为 n+1 的数组即可：
public static int levenshteinDistanceOptimized(String s1, String s2) {
if (s1.length() for (int j = 0; j <p>}</p><h3>使用 Apache Commons Text（生产推荐）</h3><p>避免重复造轮子，直接引入依赖并调用：</p><font color="gray">// Maven 依赖</font><br><pre class="brush:php;toolbar:false;"><dependency><br><groupid>org.apache.commons</groupid><br><artifactid>commons-text</artifactid><br><version>1.10.0</version><br></dependency>代码调用：
import org.apache.commons.text.similarity.LevenshteinDistance;
<p>int distance = new LevenshteinDistance().apply("kitten", "sitting"); // 返回 3
// 或指定最大阈值（提前终止，提升性能）
int distanceLimited = new LevenshteinDistance(2).apply("kitten", "sitting"); // 返回 -1（超限）
</p>Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
