ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode72. 编辑间隔（2024冬季每日一题 37） [打印本页]

---

作者: 梦应逍遥    时间: 2024-12-21 03:56
标题: LeetCode72. 编辑间隔（2024冬季每日一题 37）
给你两个单词 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’)
  提示：

•                                         0                            <                            =                            w                            o                            r                            d                            1.                            l                            e                            n                            g                            t                            h                            ,                            w                            o                            r                            d                            2.                            l                            e                            n                            g                            t                            h                            <                            =                            500                                  0 <= word1.length, word2.length <= 500                     0<=word1.length,word2.length<=500
  
• word1 和 word2 由小写英文字母组成
  

---

思绪：动态规划

• 字符串 word1 的长度为 n，word2 的长度 为 m
  
• 定义 f[j] 为将字符串 word1[1…i] 转换为 word[2…j] 所需要的最少操作次数
  
• 初始时，需要在 word1 和 word2 前面塞一个不存在的 字符，使得下标可以从 1 开始，这样后面就不需要做特别判断
  
  
  
  • j = 0时，f[0] 表现将字符串 word[1…i] 转换为空字符串需要的最短操作次数，显然，可以删除全部字符，使其变为空，所以操作次数 f[0] = i
    
  • i = 0时，f[0][j] 表现将字符串 空字符串 转换为 word2[1…j] 需要的最短操作次数，显然，可以每次添加一个字符，使其变为word[1…j]，所以操作次数 f[0][j] = j
    
  
  
• f[j] 的状态转移方程可以进行如下定义：
  
  
  
  • 如果 word1 == word[j]，说明它们的末了一个字符相等，不用任何操作，则 f[j] = f[i-1][j-1]，如果 word1 != word[j]，则需要修改word1 的末了一个字符 f[j] = f[i-1][j-1] + 1
    
  • 如果 word1 -> word2[j] 需要添加一个字符，则说明 word1[1…i] == word2[1…j-1] 则 f[j-1] + 1
    
  • 如果 word1 -> word2[j] 需要删除一个字符，则说明 word1[1…i-1] == word2[1…j] 则 f[i-1][j] + 1
    
  
  
• 所以终极 f[j] 取上面几种环境的最小值即可，则有
  f[j] = min(f[i-1][j], f[j-1]) + 1;
  f[j] = min(f[j], f[i-1][j-1] + (word1 != word2[j]));
  

1. class Solution {
2. public:
3.     int f[510][510];
4.     int minDistance(string word1, string word2) {
5.         int n = word1.size(), m = word2.size();
6.         word1 = "#" + word1, word2 = "#" + word2;
7.         memset(f, 0x3f, sizeof f);
8.         for(int i = 0; i <= n; i++) f[i][0] = i;
9.         for(int j = 0; j <= m; j++) f[0][j] = j;
10.         for(int i = 1; i <= n; i++){
11.             for(int j = 1; j <= m; j++){
12.                 f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
13.                 f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i] != word2[j]));
14.             }
15.         }
16.         return f[n][m];
17.     }
18. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4