AlgoPressAppearance
0583-两个字符串的删除操作
https://leetcode.cn/problems/delete-operation-for-two-strings
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
提示：
- 1 <= word1.length, word2.length <= 500
- word1 和 word2 只包含小写英文字母
思路
动态规划 dp[i,j] 表示 word1 前i位 变成 word2 前j为所需要的的最小步数 当比较的字符相等时 dp[i,j] = dp[i-1,j-1] 因为最后一步不需变动 当比较的字符不相等是 dp[i,j] = min(dp[i,j-1],dp[i-1,j]) + 1 前面从 s 变成 t ，还是t变成s的步数哪个小，然后再加上删除最后一个字符的操作。 注意初始化的时候
csharp
public class Solution {
public int MinDistance(string word1, string word2) {
int m = word1.Length;
int n = word2.Length;
int[,] dp = new int[m+1,n+1];
//从n个到0个就是n步
for(int i=1;i<=m;i++){
dp[i,0] = i;
}
for(int j=1;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] = Math.Min(dp[i-1,j],dp[i,j-1])+1;
}
}
}
return dp[m,n];
}
}
复习:20220515
csharp
public class Solution {
public int MinDistance(string word1, string word2) {
//动态规划，定义 dp[i,j] 表示 word1 前i个字符和 word2 前j个字符，需要删除的次数
int m = word1.Length;
int n = word2.Length;
int[,] dp = new int[m+1,n+1];
//初始化
for(int i=1; i<=m; i++){
dp[i,0] = i; //几个字符需要删除几次
}
for(int j=1; 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] = Math.Min(dp[i,j-1],dp[i-1,j]) + 1; //看从哪一边删除的次数少，然后加上删除最后一个字符的操作。
}
}
}
return dp[m,n];
}
}