代码训练LeetCode(6)编辑距离

代码训练(6)LeetCode之编辑距离

Author: Once Day Date: 2024年3月9日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 72. 编辑距离 – 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

• • • 代码训练(6)LeetCode之编辑距离
    • • 1. 原题
      • 2. 分析
      • 3. 代码实现
      • 4. 总结

1. 原题

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

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

例如对于horse和ros两个单词，其最少操作数为3，即如下三步:

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

2. 分析

这种表面一看，似乎是个字符串问题，但是如果按照分类匹配去做，怕是很难得出合理的方法。求两个字符串的编辑距离实际是个动态规划入门题目，动态规划算法是解决这个问题的标准方法。

我们先从逻辑分析一下，对于两个字符串，如horse和ros，在三种操作下，其最小操作数有下述四种情况:

1. 已知字符串hors和ros的最小操作数，然后再删除一个字母e，即: MinOperation["hors"]["ros"] + 1。
2. 已知字符串horse和ro的最小操作数，然后再增加一个字母s，即: MinOperation["horse"]["ro"] + 1。
3. 已知字符串hors和ro的最小操作数，然后再替换一个字母e -> s，即: MinOperation["hors"]["ro"] + 1。
4. 已知字符串hors和ros的最小操作数，如果最后一个字母相同，则不变，即: MinOperation["hors"]["ros"]。

第四种情况为特殊情况，即无需替换，通过上面分类讨论思想，可以发现，MinOperation["horse"]["ros"]取决于其单词前面字符的最小操作，这点很好理解，因为最后一个操作，一定是上述四种操作之一。

我们用i代表horse前i个字符组成的子字符串，j代表ros前j个字符组成的子字符串，则存在下述表达式:

MinOperation[i][j] = Min(
	(MinOperation[i-1][j] + 1), 
	(MinOperation[i][j-1] + 1), 
    (MinOperation[i-1][j-1] + 1(如果不相等)))

不断递归迭代下去，我们只要确定边界条件，则可按照递推关系求解任意i和j值的最小操作数，如下:

1. 当i = 0时，即MinOperation[0][j] = j，因为word1是空字符串，直接增加j个字符后变成word2。
2. 当j = 0时，即MinOperation[i][0] = i，因为word2是空字符串，直接删除i个字符后变成word2。
3. 当i = j = 0时，即MinOperation[0][0] = 0，都是空字符串。

下面创建一个二维数组 dp，其中 dp[i][j] 表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的最小操作数。

1. 初始化边界条件：dp[i][0] 和 dp[0][j] 分别表示将 word1 的前 i 个字符全部删除和将 word2 的前 j 个字符全部插入到 word1。
2. 遍历word1和word2的每个字符:
   • 如果当前字符相同，则 dp[i][j] = dp[i-1][j-1]。
   • 如果字符不同，我们需要考虑三种情况：
     • 插入一个字符：dp[i][j] = dp[i][j-1] + 1
     • 删除一个字符：dp[i][j] = dp[i-1][j] + 1
     • 替换一个字符：dp[i][j] = dp[i-1][j-1] + 1
   • 我们取这三种情况的最小值作为 dp[i][j] 的结果。
3. 最后 dp[length(word1)][length(word2)] 就是我们要找的答案。

按照这个算法我们可以逐步算出不同i和j值的最小操作数，如下表所示:

(1) 首先构建初始化边界条件，即i和j都为0的情况。

(2) 然后我们可以按照从左到右，从上到下，依次遍历整个表格，直到填满整个表格。

通过上表可以看出来，依次遍历整张表格的流程，也就揭示了操作的流程。

本次问题的性能优化关键点如下:

• 空间优化：如果我们只关心最终的编辑距离，不需要回溯操作路径，则可以只保留 dp 数组的两行来节省空间。
• 代码优化：确保循环和逻辑判断尽可能简洁，避免不必要的计算。

3. 代码实现

int minDistance(char * word1, char * word2){
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len1 + 1][len2 + 1];

    if (len1 == 0) {
        return len2;
    }
    if (len2 == 0) {
        return len1;
    }
    
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + (dp[i - 1][j - 1] < dp[i][j - 1] ?
                                (dp[i - 1][j - 1] < dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j]) :
                                (dp[i][j - 1] < dp[i - 1][j]? dp[i][j - 1] : dp[i - 1][j]));
            }
        }
    }

    return dp[len1][len2];
}

上面的 C 语言代码实现了编辑距离算法：

• minDistance 函数用于计算并返回编辑距离。
• len1 和 len2 分别是两个输入单词的长度。
• dp 是一个二维数组，用于存储到当前位置为止的最小编辑距离。
• 初始化 dp 数组的第一行和第一列，这表示一个字符串转换成空字符串所需的步骤数。
• 接下来的双层 for 循环用于填充 dp 数组的剩余部分。
• 我们使用嵌套的三元运算符来找到插入、删除和替换操作中的最小值。
• 函数最后返回 dp[len1][len2]，即将 word1 转换为 word2 所需的最小操作数。

下面是运行结果图(数据仅供参考，不具备实际意义):

4. 总结

本题主要考察了动态规划的理解和应用能力。动态规划是一个非常强大的工具，它可以解决许多看似复杂的问题，将问题分解成一系列子问题，并且保证每个子问题只解决一次，保存其解以避免重复计算。

要提高解决这类问题的能力，我们应该：

• 理解动态规划的基本概念，如状态转移方程、边界条件等。
• 练习各种不同类型的动态规划问题，从简单到复杂逐渐提升。
• 学会如何将问题分解为子问题，并识别出子问题之间的依赖关系。
  的问题，将问题分解成一系列子问题，并且保证每个子问题只解决一次，保存其解以避免重复计算。