代码随想录算法训练营第四十五天|LeetCode115.不同的子序列、LeetCode583.两个字符串的删除操作、LeetCode72.编辑距离

前言

打卡代码随想录算法训练营第49期第四十五天ε(*′･∀･｀)зﾞ

首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第49期的训练营大家庭一起进步。

LeetCode115 不同的子序列

题目链接：115 不同的子序列

文章讲解：不同的子序列

视频讲解：卡哥讲解 —— 不同的子序列

本题依然是子序列问题，还是更难了一点点。

public class Solution {
    public int NumDistinct(string s, string t) {
         //dp数组含义：以i-1为结尾的s字符串中有以j-1为结尾的t字符串dp[i , j]个
        int[ , ] dp = new int[s.Length + 1 , t.Length + 1];
        //初始化
        for(int i = 0; i < s.Length; i++)
            dp[i , 0] = 1;
        for(int i = 1; i <= s.Length; i++)
        {
            for(int j = 1; j <= t.Length; j++)
            {
                //递推公式
                if(s[i - 1] == t[j - 1])
                    dp[i , j] = dp[i - 1 , j - 1] + dp[i - 1 , j];
                else
                    dp[i , j] = dp[i - 1 , j];
            }
        }
        return dp[s.Length , t.Length];
    }
}

LeetCode583 两个字符串的删除操作

题目链接：583 两个字符串的删除操作

文章讲解：两个字符串的删除操作

视频讲解：卡哥讲解 —— 两个字符串的删除操作

本题要对两个字符串都要操作，更进一步。

public class Solution {
    public int MinDistance(string word1, string word2) {
        //dp数组含义：以i-1为s结尾的字符串中有以j-1为结尾的字符串最少删除个数为dp[i , j]个
        int[,] dp = new int[word1.Length + 1 , word2.Length + 1];
        //当j为0时 删除最少个数为i个
        for(int i = 1; i <= word1.Length; i++)
            dp[i , 0] = i;
        //当i为0时 删除最少个数为j个
        for(int j = 1; 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 , dp[i , j - 1] + 1);
            }
        }
        return dp[word1.Length , word2.Length];
    }
}

LeetCode72 编辑距离

题目链接：72 编辑距离

文章讲解：编辑距离

视频讲解：卡哥讲解 —— 编辑距离

之前的几道题目都是在给这道题做铺垫。

public class Solution {
    public int MinDistance(string word1, string word2) {
        //dp数组含义：以i-1为s结尾的字符串中有以j-1为结尾的字符串最少删除个数为dp[i , j]个
        int[,] dp = new int[word1.Length + 1 , word2.Length + 1];
        //当j为0时 删除最少个数为i个
        for(int i = 1; i <= word1.Length; i++)
            dp[i , 0] = i;
        //当i为0时 删除最少个数为j个
        for(int j = 1; 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 /*删除*/ , dp[i , j - 1] + 1/*删除*/);
                    dp[i , j] = Math.Min(dp[i - 1 , j - 1] + 1 , dp[i , j]);//替换操作
                }             
            }
        }
        return dp[word1.Length , word2.Length];
    }
}

今天的题目就是为了编辑距离，所以看一下编辑距离总结。明天见~~~