在日常开发中，你是否遇到过这样的需求：用户搜索”aple”时，系统能自动提示”apple”；对比两个DNA序列，计算它们之间的相似程度；或者实现一个简易的拼写检查器。这些场景背后，都离不开一个经典算法——编辑距离（Edit Distance），也称Levenshtein距离。它衡量的是：将一个字符串转换成另一个字符串所需的最少编辑操作次数（插入、删除、替换）。本文将用Java完整实现这一算法，从基础DP到空间优化，逐步深入。
一、问题定义与编辑操作
给定两个字符串 source 和 target，我们可以执行三种操作：
- 插入：在
source中插入一个字符 - 删除：从
source中删除一个字符 - 替换：将
source中的某个字符替换为另一个字符
每种操作的代价通常为1。编辑距离就是使两个字符串相等的最小总代价。
1.1 直观示例
| source | target | 编辑距离 | 操作序列 |
|---|---|---|---|
| horse | ros | 3 | horse→rorse→rose→ros (替换h→r, 删除r, 删除e) |
| intention | execution | 5 | 删除t, 替换i→e, 替换n→x, 插入u, 替换n→c |
| apple | aple | 1 | 插入p |
二、动态规划解法
2.1 状态定义
设 dp[i][j] 表示将 source[0..i-1] 转换为 target[0..j-1] 所需的最小编辑距离。
2.2 状态转移方程
对于 dp[i][j]，考虑 source[i-1] 和 target[j-1] 的关系：
- 若两者相等：
dp[i][j] = dp[i-1][j-1]（无需操作） - 若不相等，取三种操作的最小值：
- 删除：
dp[i-1][j] + 1 - 插入：
dp[i][j-1] + 1 - 替换：
dp[i-1][j-1] + 1
综上：
if source[i-1] == target[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
2.3 边界条件
dp[0][j] = j：将空串转为target[0..j-1]，需要插入j次dp[i][0] = i：将source[0..i-1]转为空串，需要删除i次
2.4 Java实现
/**
* 编辑距离（Levenshtein Distance）基础实现
* 时间复杂度: O(m * n)
* 空间复杂度: O(m * n)
*/
public class EditDistance {
/**
* 计算两个字符串的编辑距离
*
* @param source 源字符串
* @param target 目标字符串
* @return 最小编辑距离
*/
public static int calculate(String source, String target) {
int m = source.length();
int n = target.length();
// dp[i][j] 表示 source[0..i-1] 转为 target[0..j-1] 的最小代价
int[][] dp = new int[m + 1][n + 1];
// 边界：source为空，只能插入
for (int j = 0; j <= n; j++) {
dp[0][j] = j;
}
// 边界：target为空，只能删除
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 (source.charAt(i - 1) == target.charAt(j - 1)) {
// 字符相同，无需操作
dp[i][j] = dp[i - 1][j - 1];
} else {
// 取删除、插入、替换三者最小值 + 1
int deleteCost = dp[i - 1][j] + 1; // 删除source[i-1]
int insertCost = dp[i][j - 1] + 1; // 在source中插入target[j-1]
int replaceCost = dp[i - 1][j - 1] + 1; // 替换source[i-1]为target[j-1]
dp[i][j] = Math.min(deleteCost, Math.min(insertCost, replaceCost));
}
}
}
return dp[m][n];
}
/**
* 打印DP表，便于调试和理解算法过程
*/
public static void printDPTable(String source, String target) {
int m = source.length();
int n = target.length();
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (source.charAt(i - 1) == target.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
}
System.out.print(" ");
for (int j = 0; j <= n; j++) {
System.out.printf("%4s", j == 0 ? "∅" : target.charAt(j - 1));
}
System.out.println();
for (int i = 0; i <= m; i++) {
System.out.printf("%4s ", i == 0 ? "∅" : source.charAt(i - 1));
for (int j = 0; j <= n; j++) {
System.out.printf("%4d", dp[i][j]);
}
System.out.println();
}
}
}
三、空间优化：从二维到一维
观察状态转移方程，dp[i][j] 仅依赖于当前行 dp[i][..] 和上一行 dp[i-1][..]。因此可以将空间复杂度从 O(m*n) 优化到 O(min(m,n))。
3.1 优化思路
使用一维数组 dp[j] 存储当前行的值，并用一个变量 prev 保存 dp[i-1][j-1]（对角线值）。
状态转移变为：
– 先保存 dp[j] 的旧值到临时变量 temp（这是上一行的 dp[i-1][j]）
– 更新 dp[j] 时，dp[j-1] 已经是当前行的值（插入操作的代价），prev 是 dp[i-1][j-1]（替换操作的代价），temp 是上一行的 dp[i-1][j]（删除操作的代价）
– 更新后将 prev 设为 temp（为下一列的对角线做准备）
3.2 空间优化版Java实现
/**
* 编辑距离空间优化实现
* 时间复杂度: O(m * n)
* 空间复杂度: O(min(m, n))
*/
public class EditDistanceOptimized {
/**
* 计算编辑距离（空间优化版）
* 始终使用较短的字符串作为列维度，最小化空间占用
*/
public static int calculate(String source, String target) {
// 确保 source 是较短的字符串，以最小化空间
if (source.length() > target.length()) {
String temp = source;
source = target;
target = temp;
}
int m = source.length();
int n = target.length();
// 一维DP数组，长度取较短字符串 + 1
int[] dp = new int[m + 1];
// 初始化：将空串转为 source[0..i-1] 需要 i 次删除
for (int i = 0; i <= m; i++) {
dp[i] = i;
}
// 逐行处理 target 的每个字符
for (int j = 1; j <= n; j++) {
int prev = dp[0]; // 保存 dp[i-1][j-1]，初始为 dp[0][0]
dp[0] = j; // 当前行第0列：将空串转为 target[0..j-1] 需 j 次插入
for (int i = 1; i <= m; i++) {
int temp = dp[i]; // 保存上一行的 dp[i][j]（删除代价的来源）
if (source.charAt(i - 1) == target.charAt(j - 1)) {
dp[i] = prev; // 字符相同，继承对角线值
} else {
int deleteCost = temp + 1; // 上一行同列 + 1
int insertCost = dp[i - 1] + 1; // 当前行前一列 + 1
int replaceCost = prev + 1; // 对角线 + 1
dp[i] = Math.min(deleteCost, Math.min(insertCost, replaceCost));
}
prev = temp; // 更新对角线值为上一行的当前列值
}
}
return dp[m];
}
}
3.3 为什么可以优化到O(min(m,n))？
DP表是一个 (m+1) x (n+1) 的矩阵。由于每行计算仅依赖上一行，我们可以：
1. 只保留两行（滚动数组）：空间 O(2n) = O(n)
2. 进一步压缩到一维数组：空间 O(n)
3. 如果 m > n，可以先交换两个字符串，使列数始终为 min(m,n)
这样即使处理两个长度均为10万的字符串，空间也仅需约400KB（int[100001]），完全可以接受。
四、完整测试与验证
public class Main {
public static void main(String[] args) {
// 测试用例1：经典示例
test("horse", "ros", 3);
// 测试用例2：替换+插入+删除混合
test("intention", "execution", 5);
// 测试用例3：单字符差异
test("apple", "aple", 1);
// 测试用例4：完全相同的字符串
test("algorithm", "algorithm", 0);
// 测试用例5：空串
test("", "abc", 3);
// 测试用例6：完全不相交
test("abc", "def", 3);
// 测试用例7：较长字符串
test("kitten", "sitting", 3);
// 打印DP表，可视化理解
System.out.println("\n=== DP表可视化: horse -> ros ===");
EditDistance.printDPTable("horse", "ros");
System.out.println("\n=== DP表可视化: apple -> aple ===");
EditDistance.printDPTable("apple", "aple");
}
private static void test(String source, String target, int expected) {
int result1 = EditDistance.calculate(source, target);
int result2 = EditDistanceOptimized.calculate(source, target);
boolean pass = (result1 == expected) && (result2 == expected);
System.out.printf("[%s] \"%s\" -> \"%s\": 期望=%d, 基础版=%d, 优化版=%d%n",
pass ? "PASS" : "FAIL", source, target, expected, result1, result2);
}
}
运行结果：
[PASS] "horse" -> "ros": 期望=3, 基础版=3, 优化版=3
[PASS] "intention" -> "execution": 期望=5, 基础版=5, 优化版=5
[PASS] "apple" -> "aple": 期望=1, 基础版=1, 优化版=1
[PASS] "algorithm" -> "algorithm": 期望=0, 基础版=0, 优化版=0
[PASS] "" -> "abc": 期望=3, 基础版=3, 优化版=3
[PASS] "abc" -> "def": 期望=3, 基础版=3, 优化版=3
[PASS] "kitten" -> "sitting": 期望=3, 基础版=3, 优化版=3
=== DP表可视化: horse -> ros ===
∅ r o s
∅ 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
=== DP表可视化: apple -> aple ===
∅ a p l e
∅ 0 1 2 3 4
a 1 0 1 2 3
p 2 1 0 1 2
p 3 2 1 1 2
l 4 3 2 1 2
e 5 4 3 2 1
五、实际应用场景：简易拼写检查器
编辑距离最直接的应用就是拼写纠错。以下是一个基于编辑距离的最小编辑候选查找器：
import java.util.*;
/**
* 基于编辑距离的简易拼写检查器
* 从词典中找出与输入词编辑距离最小的候选词
*/
public class SpellChecker {
private final List<String> dictionary;
public SpellChecker(List<String> dictionary) {
this.dictionary = dictionary;
}
/**
* 查找词典中与输入词编辑距离最小的前k个候选词
*/
public List<Candidate> suggest(String word, int topK) {
PriorityQueue<Candidate> maxHeap = new PriorityQueue<>(
(a, b) -> Integer.compare(b.distance, a.distance)
);
for (String candidate : dictionary) {
int dist = EditDistanceOptimized.calculate(word, candidate);
maxHeap.offer(new Candidate(candidate, dist));
if (maxHeap.size() > topK) {
maxHeap.poll(); // 移除距离最大的
}
}
List<Candidate> result = new ArrayList<>(maxHeap);
result.sort(Comparator.comparingInt(c -> c.distance));
return result;
}
public record Candidate(String word, int distance) {
@Override
public String toString() {
return word + "(距离=" + distance + ")";
}
}
public static void main(String[] args) {
List<String> dict = Arrays.asList(
"apple", "apply", "ape", "apart", "appeal",
"orange", "banana", "grape", "application", "approach"
);
SpellChecker checker = new SpellChecker(dict);
String input = "aple";
System.out.println("输入: " + input);
System.out.println("拼写建议: " + checker.suggest(input, 3));
}
}
运行结果：
输入: aple
拼写建议: [ape(距离=1), apple(距离=1), apply(距离=2)]
六、复杂度总结
| 实现版本 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 基础DP（二维数组） | O(m × n) | O(m × n) | 需要回溯编辑路径、理解算法过程 |
| 滚动数组（两行） | O(m × n) | O(2 × min(m,n)) | 中等空间约束 |
| 一维数组（最优） | O(m × n) | O(min(m,n)) | 大字符串比对、生产环境 |
七、进阶拓展
编辑距离是字符串相似度计算的基石。在此基础上，可以进一步探索：
- Damerau-Levenshtein距离：增加”相邻字符交换”操作（代价为1），更符合人类拼写错误习惯
- 加权编辑距离：不同操作的代价不同（如键盘上相邻字母替换代价更低）
- 最长公共子序列（LCS）：与编辑距离密切相关，
LCS长度 = (m + n - 编辑距离) / 2（当仅考虑插入删除时） - Jaccard相似度：结合n-gram用于大规模文本模糊匹配
掌握编辑距离，你就掌握了字符串相似度计算的”瑞士军刀”。无论是搜索引擎的纠错提示、生物信息学的序列比对，还是代码diff工具的核心逻辑，这个看似简单的DP算法都在默默发挥着巨大作用。
