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
word1取[0..0]的时候,word1为空字符串“”;word2只能删除全部字符,或者word2替换全部字符为 " " 空字符串,或者word1插入和word2一样的字符
同理word2取[0..0]的时候也是
vectorint>>> dp(M + 1, vectorint>>(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(); vectorint>>> dp(M + 1, vectorint>>(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(); vectorint>>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]; } };