两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode）

因为两个字符串都能删除，所以字符不匹配的话就有三个方向取最小值赋值给dp[i,j]，不过这里dp[i-1,j-1]+2=dp[i,j-1]+1，从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]，dp[i][j-1] 本来就不考虑 word2[j - 1]了，那么我在删 word1[i - 1]，是不是就达到两个元素都删除的效果，即 dp[i][j-1] + 1。（抄的，还是没搞懂，只能不省略三个方向一起写）

初始化，设某个字符串是空的，另一个字符串有多长就得删除多少次。

public class Solution {
    public int MinDistance(string word1, string word2) {
        int[,] dp = new int[word1.Length+1,word2.Length+1];
        for(int i=0;i<=word1.Length;i++)dp[i,0] = i;
        for(int j=0;j<=word2.Length;j++)dp[0,j] = j;

        for(int i=1;i<=word1.Length;i++){
            for(int j=1;j<=word2.Length;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-1]+2,Math.Min(dp[i,j-1]+1,dp[i-1,j]+1));
                }
            }
        }
        return dp[word1.Length,word2.Length];
    }
}

 编辑距离

72. 编辑距离 - 力扣（LeetCode）

递推公式，和上一题差不多，多了增、改，但增其实也是删，如果增的是word1，那删的是word2，例如word1：abc，word2：abcd。word1增加d的操作数和word2删除d的操作数是一样的。改的话，就是多加一步才得到目标字符。所以，当字符不同时，总共有三个方向，dp[i,j] = Math.Min(dp[i-1,j-1]+1,Math.Min(dp[i,j-1],dp[i-1,j])+1);

public class Solution {
    public int MinDistance(string word1, string word2) {
        int[,] dp = new int[word1.Length+1,word2.Length+1];
        for(int i=0;i<=word1.Length;i++)dp[i,0] = i;
        for(int j=0;j<=word2.Length;j++)dp[0,j] = j;

        for(int i=1;i<=word1.Length;i++){
            for(int j=1;j<=word2.Length;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-1]+1,Math.Min(dp[i,j-1],dp[i-1,j])+1);
                }
            }
        }
        return dp[word1.Length,word2.Length];
    }
}