编辑距离算法
1.题目
给你两个单词
word1
和
word2
， 请返回将
word1
转换成
word2
所使
用的最少操作数
。
你可以对一个单词进行如下三种操作：
- 删除一个字符
- 替换一个字符
- 插入一个字符
示例：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')链接：https://leetcode.cn/problems/edit-distance/description/
2.分析
可以转化为一道多维的动态规划问题，在
两个字符串的删除操作
的基础上添加了删除和替换操作。我们可以在二维的基础上额外添加一个变量来表示操作类型
k = 0，删除操作，k = 1替换操作，k = 2插入操作
1.确定dp数组
dp[i][j][k] 表示在word1 [0..i] ，word2 [0..j] 的子串执行k操作后满足两个字符串相等的最小操作数，k = 0,1,2
例如：
word1 = "h" ， word2 = "r"，dp[1][1][0] 表示执行删除操作后，word1 和 word2 相等的最小操作数，显然 dp[1][1][0] = 2
要记住 k 操作对应的是最后一个操作
在使用动态规划的时候，
在清晰 dp[i][j]考虑的是 i，j是末尾的状态的值，不要去考虑对别的值的影响，
例如 dp[k][p] (k ≥ i 和 p≥ j的情况)
2.确定转换公式
转换可以分为两个情况， word1[i] == word2[j] 和 word1[i] ≠ word2[j]
1.word1[i] == word2[j]
如果 word1[i] == word2[j]了，那么我们其实不需要进行任何操作，此时取前一个状态的最小值就好
int tmp = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]);
dp[i][j][0] = tmp;
dp[i][j][1] = tmp;
dp[i][j][2] = tmp;2.word1[i] ≠ word2[j]
word1[i] ≠ word2[j]时，可以拆分为插入，删除和替换三种情况
2.1 删除
删除操作对应dp[i][j]时删除 i 或者 删除 j，那么只要考虑 dp[i-1][j]，dp[i][j-1]的情况即可（注意这里 dp[i-1][j]，dp[i][j-1] 都可能进行多种操作）
int tmp2 = min(min(dp[i - 1][j][1], dp[i - 1][j][2]), dp[i - 1][j][0]);
int tmp3 = min(min(dp[i][j-1][1], dp[i][j-1][2]), dp[i][j-1][0]);
dp[i][j][0] = min(tmp2, tmp3) + 1;2.2 替换
对于[i][j]进行替换，那么我们只需要替换 i 或者 替换 j 就可以了，替换就是在 [0..i-1] [0..j-1]的基础上，加上一个操作使得 i == j
int tmp1 = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]);
dp[i][j][1] = tmp1 + 1;2.3 插入
对于插入操作，本质和删除一致的，为什么这么说呢？
word1[i] ≠ word2[j]，我们只能在 i 或者 j 的尾部进行插入，即 i-1 插入字符 char 使得 char == word2[j]；或者 j-1 位置插入字符 char 使得 char == word1[i]
如果在 i 或者 j后面插入，
我们还需要额外进行一次删除操作，
因此插入操作代码和删除一致，这里可以进行优化
int tmp2 = min(min(dp[i - 1][j][1], dp[i - 1][j][2]), dp[i - 1][j][0]);
int tmp3 = min(min(dp[i][j-1][1], dp[i][j-1][2]), dp[i][j-1][0]);
dp[i][j][2] = min(tmp2, tmp3) + 1;3. 初始化
考虑到dp会用到前面的数据，便于递推额外添加一个大小，因此 dp初始化为 vector<vector<vector<int>>> dp(word1.size() + 1, vector<vector<int>>(word2.size()+ 1, vector<int>(3)));
word1取[0..0]的时候，word1为空字符串“”；word2只能删除全部字符，或者word2替换全部字符为 " " 空字符串，或者word1插入和word2一样的字符
同理word2取[0..0]的时候也是
vector<vector<vector<int>>> dp(M + 1, vector<vector<int>>(N + 1, vector<int>(3)));
//每一步都可能执行不同的操作 这时候替换表示地替换成 "" 空字符串，插入表示对另一边进行插入
for (int i = 0; i <= M; ++i)
{
dp[i][0][0] = i;
dp[i][0][1] = i;
dp[i][0][2] = i;
}
for (int j = 0; j <= N; ++j)
{
dp[0][j][0] = j;
dp[0][j][1] = j;
dp[0][j][2] = j;
}3. 代码实现
class Solution {
public:
int minDistance(string word1, string word2) {
//dp[i][j][k] 表示 [0..i] [0..j]相同所需的最少操作符 k表示执行这个操作时最小值
//最后只需要对三个数 求最小值
const int M = word1.size();
const int N = word2.size();
vector<vector<vector<int>>> dp(M + 1, vector<vector<int>>(N + 1, vector<int>(3)));
//每一步都可能执行不同的操作 这时候替换表示地替换成 "" 空字符串，插入表示对另一边进行插入
// 0-插入 1 -删除 2-替换
for (int i = 0; i <= M; ++i)
{
dp[i][0][0] = i;
dp[i][0][1] = i;
dp[i][0][2] = i;
}
for (int j = 0; j <= N; ++j)
{
dp[0][j][0] = j;
dp[0][j][1] = j;
dp[0][j][2] = j;
}
for (int i = 1; i <= M; ++i)
{
for (int j = 1; j <= N; ++j)
{
if (word1[i-1] == word2[j-1])
{
int tmp = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]);
dp[i][j][0] = tmp;
dp[i][j][1] = tmp;
dp[i][j][2] = tmp;
}
else
{
int tmp2 = min(min(dp[i - 1][j][1], dp[i - 1][j][2]), dp[i - 1][j][0]);
int tmp3 = min(min(dp[i][j-1][1], dp[i][j-1][2]), dp[i][j-1][0]);
dp[i][j][0] = min(tmp2, tmp3) + 1;
//替换 在i-1,j-1的基础上，替换值
int tmp1 = min(min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]), dp[i - 1][j - 1][2]);
dp[i][j][1] = tmp1 + 1;
//插入 - 最优情况只能在少的一边插入，否则会增加一个删除操作
//删除和插入本质应该一致，因为都应该在尾部插，否则增加额外一个删除操作
dp[i][j][2] = dp[i][j][0];
}
}
}
return min(min(dp[M][N][0], dp[M][N][1]), dp[M][N][2]);
}
};4.优化
上面分成三个状态推导为了方便理解，优化情况下不需要同时考虑三个操作，只需要考虑 dp[i][j]的变化即可（其实就是对操作进行合并）
class Solution {
public:
int minDistance(string word1, string word2) {
//优化
const int M = word1.size();
const int N = word2.size();
vector<vector<int>>dp(M + 1, vector<int>(N + 1));
for (int i = 0; i <= M; ++i)
dp[i][0] = i;
for (int j = 0; j <= N; ++j)
dp[0][j] = j;
for (int i = 1; i <= M; ++i)
{
for (int j = 1; j <= N; ++j)
{
if (word1[i - 1] == word2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1]; //不进行任何操作
}
else
{
dp[i][j] = min({ dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1] }) + 1;
}
}
}
return dp[M][N];
}
};