动态规划7：编辑距离问题

引言

在动态规划系列的前六篇文章中，我们分别学习了爬楼梯问题、最长公共子序列、01背包问题、最长递增子序列、不同路径问题和股票买卖问题。今天我们将探讨动态规划中另一个重要且实用的问题——编辑距离问题。

编辑距离（Edit Distance），也称为Levenshtein距离，是衡量两个字符串相似度的重要指标。它在文本处理、DNA序列分析、拼写检查、机器翻译等领域有着广泛的应用。通过学习这个问题，我们将深入理解动态规划在字符串处理中的强大能力。

问题定义

什么是编辑距离？

编辑距离：将一个字符串转换为另一个字符串所需的最少编辑操作次数。

允许的编辑操作包括：

1. 插入（Insert）：在字符串中插入一个字符
2. 删除（Delete）：从字符串中删除一个字符
3. 替换（Replace）：将字符串中的一个字符替换为另一个字符

经典例题

LeetCode 72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

算法分析

1. 暴力递归思路

对于两个字符串 word1[0...i-1] 和 word2[0...j-1]，我们可以这样分析：

• 如果 word1[i-1] == word2[j-1]，那么问题转化为 word1[0...i-2] 和 word2[0...j-2] 的编辑距离
• 如果 word1[i-1] != word2[j-1]，我们有三种选择：
  1. 替换：将 word1[i-1] 替换为 word2[j-1]，问题转化为 word1[0...i-2] 和 word2[0...j-2] 的编辑距离 + 1
  2. 删除：删除 word1[i-1]，问题转化为 word1[0...i-2] 和 word2[0...j-1] 的编辑距离 + 1
  3. 插入：在 word1 末尾插入 word2[j-1]，问题转化为 word1[0...i-1] 和 word2[0...j-2] 的编辑距离 + 1

2. 动态规划解法

状态定义

定义 dp[i][j] 表示：将 word1[0...i-1] 转换为 word2[0...j-1] 的最少操作数。

状态转移方程

如果 word1[i-1] == word2[j-1]：
    dp[i][j] = dp[i-1][j-1]
否则：
    dp[i][j] = 1 + min(
        dp[i-1][j-1],    // 替换
        dp[i-1][j],      // 删除
        dp[i][j-1]       // 插入
    )

边界条件

• dp[0][j] = j：空字符串转换为长度为 j 的字符串需要 j 次插入操作
• dp[i][0] = i：长度为 i 的字符串转换为空字符串需要 i 次删除操作

代码实现

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    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++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    Math.min(dp[i - 1][j - 1], dp[i - 1][j]),
                    dp[i][j - 1]
                );
            }
        }
    }
    
    return dp[m][n];
}

算法复杂度

• 时间复杂度：O(m × n)，其中 m 和 n 分别是两个字符串的长度
• 空间复杂度：O(m × n)

空间优化

观察状态转移方程，我们发现 dp[i][j] 只依赖于：

• dp[i-1][j-1]（左上角）
• dp[i-1][j]（上方）
• dp[i][j-1]（左方）

因此可以使用一维数组进行空间优化：

一维DP优化

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    int[] dp = new int[n + 1];
    
    // 初始化第一行
    for (int j = 0; j <= n; j++) {
        dp[j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];  // 保存dp[i-1][j-1]的值
        dp[0] = i;         // dp[i][0] = i
        
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[j] = prev;
            } else {
                dp[j] = 1 + Math.min(Math.min(prev, dp[j]), dp[j - 1]);
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

优化后的空间复杂度：O(min(m, n))

算法可视化理解

让我们通过示例 word1 = "horse", word2 = "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[0][0] = 0：空字符串到空字符串不需要操作
• dp[1][1] = 1："h" 到 "r" 需要1次替换
• dp[2][2] = 1："ho" 到 "ro" 只需替换h为r
• dp[5][3] = 3：最终答案，需要3次操作

构造具体的编辑序列

如果我们不仅要知道最少操作数，还要知道具体的操作序列，可以在DP的基础上添加路径记录：

public List<String> getEditSequence(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    int[][] dp = new int[m + 1][n + 1];
    int[][] path = new int[m + 1][n + 1]; // 0:匹配, 1:替换, 2:删除, 3:插入
    
    // 初始化
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
        path[i][0] = 2; // 删除
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
        path[0][j] = 3; // 插入
    }
    
    // 填充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];
                path[i][j] = 0; // 匹配
            } else {
                int replace = dp[i - 1][j - 1];
                int delete = dp[i - 1][j];
                int insert = dp[i][j - 1];
                
                if (replace <= delete && replace <= insert) {
                    dp[i][j] = replace + 1;
                    path[i][j] = 1; // 替换
                } else if (delete <= insert) {
                    dp[i][j] = delete + 1;
                    path[i][j] = 2; // 删除
                } else {
                    dp[i][j] = insert + 1;
                    path[i][j] = 3; // 插入
                }
            }
        }
    }
    
    // 构造操作序列
    List<String> operations = new ArrayList<>();
    int i = m, j = n;
    while (i > 0 || j > 0) {
        int op = path[i][j];
        switch (op) {
            case 0: // 匹配
                operations.add("Match " + word1.charAt(i - 1));
                i--; j--;
                break;
            case 1: // 替换
                operations.add("Replace " + word1.charAt(i - 1) + " with " + word2.charAt(j - 1));
                i--; j--;
                break;
            case 2: // 删除
                operations.add("Delete " + word1.charAt(i - 1));
                i--;
                break;
            case 3: // 插入
                operations.add("Insert " + word2.charAt(j - 1));
                j--;
                break;
        }
    }
    
    Collections.reverse(operations);
    return operations;
}

编辑距离的变形问题

1. 只允许插入和删除

LeetCode 583. 两个字符串的删除操作

如果只允许删除操作，问题就变成求两个字符串的最长公共子序列：

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    return m + n - 2 * longestCommonSubsequence(word1, word2);
}

2. 只允许插入

将 word1 通过插入操作变成 word2，等价于将 word2 通过删除操作变成 word1。

3. 带权重的编辑距离

不同操作有不同的代价，状态转移方程需要相应调整：

dp[i][j] = min(
    dp[i-1][j-1] + cost_replace,
    dp[i-1][j] + cost_delete,
    dp[i][j-1] + cost_insert
)

实际应用场景

编辑距离在实际开发中有着广泛的应用：

1. 文本相似度计算

public double similarity(String s1, String s2) {
    int maxLen = Math.max(s1.length(), s2.length());
    if (maxLen == 0) return 1.0;
    
    int editDistance = minDistance(s1, s2);
    return 1.0 - (double) editDistance / maxLen;
}

2. 拼写检查和纠错

public List<String> getSuggestions(String word, List<String> dictionary) {
    return dictionary.stream()
        .filter(dictWord -> minDistance(word, dictWord) <= 2)
        .collect(Collectors.toList());
}

3. DNA序列比对

在生物信息学中，编辑距离用于比较DNA、RNA或蛋白质序列的相似性。

4. 版本控制系统

Git等版本控制系统使用类似的算法来计算文件之间的差异。

优化技巧和扩展

1. 早期终止优化

如果我们只需要判断编辑距离是否小于某个阈值 k，可以进行早期终止：

public boolean isEditDistanceLessEqual(String word1, String word2, int k) {
    int m = word1.length();
    int n = word2.length();
    
    // 如果长度差超过k，直接返回false
    if (Math.abs(m - n) > k) return false;
    
    int[] dp = new int[n + 1];
    for (int j = 0; j <= n; j++) {
        dp[j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];
        dp[0] = i;
        boolean hasValidValue = false;
        
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[j] = prev;
            } else {
                dp[j] = 1 + Math.min(Math.min(prev, dp[j]), dp[j - 1]);
            }
            
            if (dp[j] <= k) hasValidValue = true;
            prev = temp;
        }
        
        // 如果当前行没有任何值小于等于k，可以早期终止
        if (!hasValidValue) return false;
    }
    
    return dp[n] <= k;
}

2. 对角线优化

当两个字符串长度相近时，可以只计算对角线附近的值，减少计算量。

算法思想总结

编辑距离问题体现了动态规划的核心思想：

1. 问题分解

将复杂的字符串转换问题分解为子问题：

• 字符匹配时，问题规模减1
• 字符不匹配时，尝试三种操作，选择最优解

2. 状态设计

二维状态 dp[i][j] 清晰地表示了子问题的含义，便于理解和实现。

3. 边界处理

空字符串的处理为递推提供了起始条件。

4. 优化策略

从二维到一维的空间优化展示了DP优化的一般思路。

复杂度对比

方法	时间复杂度	空间复杂度	特点
暴力递归	O(3^(m+n))	O(m+n)	指数级时间，不实用
二维DP	O(m×n)	O(m×n)	标准解法
一维DP	O(m×n)	O(min(m,n))	空间优化
早期终止	O(m×n)	O(min(m,n))	阈值判断优化

总结

编辑距离问题是动态规划在字符串处理领域的经典应用，它具有以下特点：

1. 实用价值高：在文本处理、生物信息学等领域应用广泛
2. 算法思想清晰：体现了动态规划分解问题、构建状态的思维方式
3. 优化空间大：可以进行空间优化和算法优化
4. 扩展性强：有多种变形问题和应用场景

通过学习编辑距离问题，我们不仅掌握了一个重要的算法，更深入理解了动态规划在实际问题中的应用模式。这种将复杂问题分解为子问题，通过状态转移求解最优解的思想，是我们解决许多实际问题的有力工具。

系列文章回顾

• 动态规划入门：从爬楼梯问题开始
• 动态规划进阶：最长公共子序列问题
• 动态规划深入：01背包问题详解
• 动态规划4：最长递增子序列问题
• 动态规划5：不同路径问题与路径计数
• 动态规划6：股票买卖问题

推荐练习

• 在LeetCode上练习更多编辑距离相关的题目
• 尝试实现带权重的编辑距离算法
• 思考编辑距离在实际项目中的应用场景
• 研究其他字符串匹配算法，如KMP、Boyer-Moore等