LeetCode 热题 100_编辑距离（94_72_中等_C++）
题目描述：
给你两个单词 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 由小写英文字母组成
题解：
解题思路：
思路一（动态规划）：
1、因我们有两个 word，可以想到二维 dp 数组。
① dp[i][j] 的含义为 word1 前 i 个字符转换为 word2 前j个字符最少的操作次数。
② dp[ i ][ j ] = dp[i-1][j-1] ,当 word1[i-1]==word2[j-1] ,当 word1 第 i 个字符和 word2 第 j 个字符相等时无需操作。
③ dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) (判断当前位置删除、添加、替换哪个操次数更少)
- dp[i-1][j] 对应 word1[i-1] 的删除操作。
- dp[i][j-1] 对应 word2[j-1] 的删除操作，和 word1 添加的功能相同。
- dp[i-1][j-1] 对应 word1[i-1] 的替换操作。
④ 通过上述定义对 dp 数组进行初始化，dp[i][0]=i ，word1 有 i 个字符 word2 有 0 个字符，word1 需删除 i 个字符。dp[0][j]=j，word2 有 j 个字符 word1 有 0 个字符，word1 需添加i个字符
2、复杂度分析：
① 时间复杂度：O(m×n)，m 和 n 分别代表 word1 和 word2 中字符的个数， 遍历一遍二维 dp 数组。
② 空间复杂度：O(m×n)，m 和 n 分别代表 word1 和 word2 中字符的个数，dp 数组所占用的空间。
代码实现
代码实现（思路一（动态规划））：
class Solution
{
public:
// 定义函数 minDistance，计算将 word1 转换为 word2 的最小编辑距离
// 编辑操作包括插入、删除和替换
int minDistance(string word1, string word2){
// 创建一个二维 DP 数组 dp，大小为 (word1.size() + 1) x (word2.size() + 1)
// dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑距离
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
// 初始化第一列，dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串的最小编辑距离
// 即需要进行 i 次删除操作
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
// 初始化第一行，dp[0][j] 表示将空字符串转换为 word2 的前 j 个字符的最小编辑距离
// 即需要进行 j 次插入操作
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
// 使用动态规划填充 dp 数组
for (int i = 1; i <= word1.size(); i++){
for (int j = 1; j <= word2.size(); j++){
// 如果当前字符相同，表示不需要进行操作
if (word1[i - 1] == word2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
} else {
// 如果当前字符不同，则需要进行插入、删除或替换操作
// 取三种操作中最小的，并加 1 表示当前操作
dp[i][j] = min(dp[i - 1][j], // 删除操作
min(dp[i][j - 1], // 插入操作
dp[i - 1][j - 1])) + 1; // 替换操作
}
}
}
// 返回 dp[word1.size()][word2.size()]，即将 word1 完全转换为 word2 的最小编辑距离
return dp[word1.size()][word2.size()];
}
};
以思路一为例进行调试
#include<iostream>
#include<vector>
using namespace std;
class Solution
{
public:
// 定义函数 minDistance，计算将 word1 转换为 word2 的最小编辑距离
// 编辑操作包括插入、删除和替换
int minDistance(string word1, string word2){
// 创建一个二维 DP 数组 dp，大小为 (word1.size() + 1) x (word2.size() + 1)
// dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑距离
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
// 初始化第一列，dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串的最小编辑距离
// 即需要进行 i 次删除操作
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
// 初始化第一行，dp[0][j] 表示将空字符串转换为 word2 的前 j 个字符的最小编辑距离
// 即需要进行 j 次插入操作
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
// 使用动态规划填充 dp 数组
for (int i = 1; i <= word1.size(); i++){
for (int j = 1; j <= word2.size(); j++){
// 如果当前字符相同，表示不需要进行操作
if (word1[i - 1] == word2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
} else {
// 如果当前字符不同，则需要进行插入、删除或替换操作
// 取三种操作中最小的，并加 1 表示当前操作
dp[i][j] = min(dp[i - 1][j], // 删除操作
min(dp[i][j - 1], // 插入操作
dp[i - 1][j - 1])) + 1; // 替换操作
}
}
}
// 返回 dp[word1.size()][word2.size()]，即将 word1 完全转换为 word2 的最小编辑距离
return dp[word1.size()][word2.size()];
}
};
int main(int argc, char const *argv[])
{
string word1="horse",word2="ros";
Solution s;
cout<<s.minDistance(word1,word2);
return 0;
}
LeetCode 热题 100_编辑距离（94_72)原题链接
欢迎大家和我沟通交流(✿◠‿◠)