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<=word1.length,word2.length<=500$
• word1 和 word2 由小写英文字母组成

---

思路：动态规划

• 字符串 word1 的长度为 n，word2 的长度 为 m

• 定义 f[i][j] 为将字符串 word1[1…i] 转换为 word[2…j] 所需要的最少操作次数

• 初始时，需要在 word1 和 word2 前面塞一个不存在的 字符，使得下标可以从 1 开始，这样后面就不需要做特殊判断

  • j = 0时，f[i][0] 表示将字符串 word[1…i] 转换为空字符串需要的最短操作次数，显然，可以删除所有字符，使其变为空，所以操作次数 f[i][0] = i
  • i = 0时，f[0][j] 表示将字符串 空字符串 转换为 word2[1…j] 需要的最短操作次数，显然，可以每次添加一个字符，使其变为word[1…j]，所以操作次数 f[0][j] = j

• f[i][j] 的状态转移方程可以进行如下定义：

  • 如果 word1[i] == word[j]，说明它们的最后一个字符相等，不用任何操作，则 f[i][j] = f[i-1][j-1]，如果 word1[i] != word[j]，则需要修改word1[i] 的最后一个字符 f[i][j] = f[i-1][j-1] + 1
  • 如果 word1[i] -> word2[j] 需要添加一个字符，则说明 word1[1…i] == word2[1…j-1] 则 f[i][j-1] + 1
  • 如果 word1[i] -> word2[j] 需要删除一个字符，则说明 word1[1…i-1] == word2[1…j] 则 f[i-1][j] + 1

• 所以最终 f[i][j] 取上面几种情况的最小值即可，则有
  f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
  f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i] != word2[j]));

class Solution {
public:
    int f[510][510];
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        word1 = "#" + word1, word2 = "#" + word2;
        memset(f, 0x3f, sizeof f);
        for(int i = 0; i <= n; i++) f[i][0] = i;
        for(int j = 0; j <= m; j++) f[0][j] = j;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
                f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i] != word2[j]));
            }
        }
        return f[n][m];
    }
};

原文地址：https://blog.csdn.net/qq_46456049/article/details/144609796

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！