字符串最小编辑距离的动态规划实现
基本原理
最小编辑距离（Levenshtein Distance）衡量的是将一个字符串转换为另一个字符串所需的最少基本操作次数。允许的操作包括：插入一个字符、删除一个字符或替换一个字符。
例如，将字符串 kitten 转换为 sitting 的过程如下：
kitten→sitten（替换 'k' 为 's'）sitten→sittin（替换 'e' 为 'i'）sittin→sitting（在末尾插入 'g'）
算法设计
采用动态规划方法构建二维表格，其中每个单元格 dp[i][j] 表示第一个字符串前 i 个字符与第二个字符串前 j 个字符之间的最小编辑距离。
初始化规则：
dp[i][0] = i：将前 i 个字符全部删除dp[0][j] = j：通过插入 j 个字符达到目标
状态转移方程：
dp[i][j] = min( dp[i-1][j] + 1, // 删除当前字符 dp[i][j-1] + 1, // 插入一个字符 dp[i-1][j-1] + (s1[i-1] == s2[j-1] ? 0 : 1) // 替换或匹配)
若两字符相同，则无需代价；否则代价为 1。此优化可避免不必要的计算。
Java 实现
public class EditDistanceCalculator {
public int calculate(String source, String target) {
int m = source.length();
int n = target.length();
// 构建 DP 表
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;
}
// 填充 DP 表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int cost = (source.charAt(i - 1) == target.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) {
EditDistanceCalculator calc = new EditDistanceCalculator();
int distance = calc.calculate("Lavensting", "Levenshtein");
System.out.println("编辑距离: " + distance); // 输出: 2
}
}
复杂度分析
- 时间复杂度：O(m × n)，其中 m 和 n 分别为两个字符串长度
- 空间复杂度：O(m × n)，可进一步优化至 O(min(m, n)) 使用滚动数组
