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

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

Author: Once Day Date: 2024年3月9日
漫漫长路，才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:

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

  
1. 原题

   给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
  你可以对一个单词举行如下三种操作：
  

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

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

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

复制代码

2. 分析

这种表面一看，好像是个字符串题目，但是如果按照分类匹配去做，怕是很惆怅出公道的方法。求两个字符串的编辑距离现实是个动态规划入门题目，动态规划算法是办理这个题目的标准方法。
我们先从逻辑分析一下，对于两个字符串，如horse和ros，在三种操作下，其最小操作数有下述四种情况:

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

第四种情况为特殊情况，即无需替换，通过上面分类讨论头脑，可以发现，MinOperation["horse"]["ros"]取决于其单词前面字符的最小操作，这点很好明确，因为最后一个操作，一定是上述四种操作之一。
我们用i代表horse前i个字符组成的子字符串，j代表ros前j个字符组成的子字符串，则存在下述表达式:

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

复制代码

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

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

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

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

按照这个算法我们可以逐步算出不同i和j值的最小操作数，如下表所示:
(1) 首先构建初始化边界条件，即i和j都为0的情况。
MinOperation(空字符串0)字符1r字符2o字符3s(空字符串0)0123字符1h1字符2o2字符3r3字符4s4字符5e5 (2) 然后我们可以按照从左到右，从上到下，依次遍历整个表格，直到填满整个表格。
MinOperation(空字符串0)字符1r字符2o字符3s(空字符串0)0123字符1h11(替换h)23字符2o221(o相当)2字符3r322(删除r)2字符4s4332(s相当)字符5e5443(删除e) 通过上表可以看出来，依次遍历整张表格的流程，也就揭示了操作的流程。
本次题目的性能优化关键点如下:

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

3. 代码实现

1. int minDistance(char * word1, char * word2){
2.     int len1 = strlen(word1);
3.     int len2 = strlen(word2);
4.     int dp[len1 + 1][len2 + 1];
6.     if (len1 == 0) {
7.         return len2;
8.     }
9.     if (len2 == 0) {
10.         return len1;
11.     }
12.    
13.     for (int i = 0; i <= len1; i++) {
14.         dp[i][0] = i;
15.     }
16.     for (int j = 0; j <= len2; j++) {
17.         dp[0][j] = j;
18.     }
20.     for (int i = 1; i <= len1; i++) {
21.         for (int j = 1; j <= len2; j++) {
22.             if (word1[i - 1] == word2[j - 1]) {
23.                 dp[i][j] = dp[i - 1][j - 1];
24.             } else {
25.                 dp[i][j] = 1 + (dp[i - 1][j - 1] < dp[i][j - 1] ?
26.                                 (dp[i - 1][j - 1] < dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j]) :
27.                                 (dp[i][j - 1] < dp[i - 1][j]? dp[i][j - 1] : dp[i - 1][j]));
28.             }
29.         }
30.     }
32.     return dp[len1][len2];
33. }

复制代码

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

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

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

4. 总结

本题主要考察了动态规划的明确和应用能力。动态规划是一个非常强大的工具，它可以办理许多看似复杂的题目，将题目分解成一系列子题目，并且包管每个子题目只办理一次，生存其解以避免重复盘算。
要进步办理这类题目的能力，我们应该：

• 明确动态规划的基本概念，如状态转移方程、边界条件等。
  
• 练习各种不同范例的动态规划题目，从简单到复杂逐渐提升。
  
• 学会怎样将题目分解为子题目，并识别出子题目之间的依赖关系。
  的题目，将题目分解成一系列子题目，并且包管每个子题目只办理一次，生存其解以避免重复盘算。
  

   Once Day

  

    也信美人终作土，不堪幽梦太匆匆......
    如果这篇文章为您带来了帮助或启发，不妨点个赞