题目

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

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

示例：

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

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

解答 & 代码

动态规划：

设置动态规划数组 dp，dp[i][j] 代表 word1 的前 i 个字符和 word2 和前 j 个字符之间的编辑距离
状态转移方程：
- insert1 = dp[i - 1][j] + 1，即原本 word1 的前 i - 1 个字符和 word2 和前 j 个字符已经匹配，要得到 dp[i][j]，那么将 word2 末尾插入一个字符即可（word2 插入相当于 word1 删除）
- insert2 = dp[i][j - 1] + 1，即原本 word1 的前 i 个字符和 word2 和前 j - 1 个字符已经匹配，要得到 dp[i][j]，那么将 word1 末尾插入一个字符即可
- replace = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1，即原本 word1 的前 i - 1 个字符和 word2 和前 j - 1 个字符已经匹配，要得到 dp[i][j]，如果 word1 的第 i 个字符和 word2 的第 j 个字符相同，那么不用再进行编辑，dp[i][j] = dp[i - 1][j - 1]；如果 word1 的第 i 个字符和 word2 的第 j 个字符不同，那么需要替换一次，因此 dp[i][j] = dp[i - 1][j - 1] + 1

初始化：

dp[i][0] = i，dp[0][i] = i，即如果有一个 word 长为 0，编辑距离就是另一个 word 的长度

class Solution {
public:
int minDistance(string word1, string word2) {
   int len1 = word1.size();
   int len2 = word2.size();
   vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
   dp[0][0] = 0;
   for(int i = 1; i <= len1; ++i)
       dp[i][0] = i;
   for(int i = 1; i <= len2; ++i)
       dp[0][i] = i;
   for(int i = 1; i <= len1; ++i)
   {
       for(int j = 1; j <= len2; ++j)
       {
           int insert1 = dp[i - 1][j] + 1;
           int insert2 = dp[i][j - 1] + 1;
           int replace = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1;
           dp[i][j] = min(min(insert1, insert2), replace);
       }
   }
   return dp[len1][len2];
}
};

复杂度分析：设两个数组长度分别为 N、M

时间复杂度 O(NM)
空间复杂度 O(NM)

执行结果：

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 64.54% 的用户
内存消耗：8.9 MB, 在所有 C++ 提交中击败了 16.18% 的用户

CodeTop 企业题库

[困难] 72. 编辑距离

题目

解答 & 代码