😄583.两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
思路
基本思想
与
392题
一样，需要将思路进行转换，从问题中发现关键的地方
本题中求的是尽可能少的删除字符串中的字符，使得两个字符串保持一致，既然要最少的删除，那么留下来的肯定是最大的，也就是可以先求两个字符串的最大公共子序列，之后两个字符串多余的元素就应该删除，这些元素的个数就是最终的答案
dp[i][j]表示以第i个元素和第j个元素结尾的两个字符串的最长公共子序列的长度
更新逻辑为：
1
2
3
4
5
6
| if(s[i]==t[j]){
dp[i+1][j+1]=dp[i][j]+1;
}
else{
dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
}
|
最终结果为：
$$
word1.size()+word2.size()-2*res
$$
删除多余的部分
执行流程
- 初始化dp数组
- 更新dp数组
- 返回最终结果
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>>dp(word1.size()+1,
vector<int>(word2.size()+1,0));
int res=0;
for(int i=0;i<word1.size();++i){
for(int j=0;j<word2.size();++j){
if(word1[i]==word2[j]){
dp[i+1][j+1]=dp[i][j]+1;
}else{
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
res=max(res,dp[i+1][j+1]);
}
}
return word1.size()+word2.size()-2*res;
}
};
|
总结
主要是懂得思维的转换，尽可能少的删除元素使得两字符串保持一致，也就是尽可能多的留下元素，而最长公共子序列就留下了最多的元素，所以核心转换成了求最长公共子序列