您现在的位置是:首页 >技术交流 >【LeetCode】583. 两个字符串的删除操作网站首页技术交流
【LeetCode】583. 两个字符串的删除操作
简介【LeetCode】583. 两个字符串的删除操作
583. 两个字符串的删除操作(中等)
思路
这道题的状态定义和 1143. 最长公共子序列
相同,「定义一个 dp 数组,其中 dp[i]表示到位置 i 为止的子序列性质,并不是必须以 i 结尾」,此时 dp 数组的最后一位即为题目所求,不需要对每个位置进行统计。
状态定义
dp[i][j]
表示到 字符串word1 的第 i 个字符为止、word2 的第 j 个字符为止,使得两个字符串相等的最小删除次数。
状态转移方程
对于本道题,遍历两个字符串的所有位置,当 i>0 且 j>0 时,考虑两种情况:
- 如果遍历到的字符相同,说明这两个字符匹配,无需进行任何操作,那么此时的最小删除次数不变,即
dp[i][j] = dp[i-1][j-1]
; - 如果遍历到的字符不同,那么肯定需要删除其中一个字符,既可以删除 word1[i],也可以删除 word2[j],所以此时的最小删除次数在原有删除次数上 +1, 即
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
。
初始化
由于在进行状态转移时,我们会用到 i-1 和 j-1 ,需要保证数组不越界,因此对边界情况进行分析:
- 当 i = 0 且 j = 0 时,如果
word2[0] == word1[i]
,说明不需要删除,所以dp[0][0] = 0
,否则两个字符都需要删除,dp[0][0] = 2
; - 当 i = 1 ~ m-1 时,固定 j = 0,即 word2 只有一个字符,如果
word1[i] == word2[0]
,说明两个字符串能够匹配,此时需要删除 word1 的其他字符,即dp[i][0] = i
; - 同理,当 j = 1 ~ n-1 时,固定 i = 0,即 word1 只有一个字符,如果
word1[0] == word2[j]
,说明两个字符串能够匹配,此时需要删除 word2 的其他字符,即dp[0][j] = j
;
最终的返回结果
显然,最终返回 dp[m-1][n-1]
,这表示到字符串word1 的第 m-1 个字符为止、word2 的第 n-1 个字符为止,使得两个字符串相等的最小删除次数。
代码
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = word1[0] == word2[0] ? 0 : 2;
for(int i=1; i<m; ++i){
if(word2[0] == word1[i]){
dp[i][0] = i;
}else{
dp[i][0] = dp[i-1][0] + 1;
}
}
for(int j=1; j<n; ++j){
if(word1[0] == word2[j]){
dp[0][j] = j;
}else{
dp[0][j] = dp[0][j-1] + 1;
}
}
for(int i=1; i<m; ++i){
for(int j=1; j<n; ++j){
if(word1[i] == word2[j]){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
}
}
}
return dp[m-1][n-1];
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。