本文主要是介绍代码随想录训练营Day 58|力扣392.判断子序列、115不同的子序列、583两个字符串的删除操作、72编辑距离,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.判断子序列
代码随想录
代码:
class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size() + 1,vector<int>(t.size() + 1,0));// 判断s和t的公共最长子序列的长度是否和s的长度相等// dp[i][j]表示下标为0~i-1的s的子数组和下标为0~j-1的子数组的最长公共子序列的长度for(int i = 1; i <= s.size(); i++){for(int j = 1; j <= t.size(); j++){if(s[i - 1] == t[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}}}if(dp[s.size()][t.size()] == s.size()){return true;}else{return false;}}
};
思路:
这题就是判断两个字符串的最长公共子序列是不是s。其实套路都一样。下面的都是copy昨天的。
dp数组的含义:dp[i][j]表示下标为0~i-1和0~j-1字符串的最长公共子序列的长度。注意到了吗,只是求这两个字符串的最长公共子序列,没有要求一定要以什么东西结尾。所以最后一个元素就是dp数组中最大的那个元素。
dp数组的初始化:dp[0][j]和dp[i][0]都没有实际意义,而且为了能够推出符合实际意义的dp[1][1]应该把这些元素初始化为0
dp数组的递推公式:如果此时的i-1和j-1下标对应的元素都相等,那就可以在dp[i - 1][j - 1]的基础上加一了。如果不相等,就说明这两元素有互斥的关系,两个元素不可能同时被选到最长公共子序列中。所以我们可以分两种情况:dp[i - 1][j]或dp[i][j - 1],取两个的最大值。
dp数组的遍历顺序:正序遍历。
2.不同的子序列
代码随想录 (programmercarl.com)
代码:
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size() + 1,vector<uint64_t>(t.size() + 1,0));// dp[i][j]表示s中下标为0~i-1的字串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法// 根据定义进行初始化// dp[0][j]表示在空串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法// 很明显没有for(int i = 0; i <= s.size(); i++){// dp[i][0]表示s中下标为0~i-1的字串有多少种删除元素后可以变成空串的方法// 很明显是一种,就是删除所有元素 dp[0][0]也满足dp[i][0] = 1;}for(int i = 1; i <= s.size(); i++){for(int j = 1; j <= t.size(); j++){if(s[i - 1] == t[j - 1]){dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];// 注意这里dp数组的含义是方法数!!!// 一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。// 一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。}else{dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()];}
};
思路:
dp数组的含义: dp[i][j]表示s中下标为0~i-1的字串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法
dp数组的初始化:dp[0][j]表示在空串中有多少种删除元素后可以变成t中下标为0~j-1的子序列的方法,很明显没有;dp[i][0]表示s中下标为0~i-1的字串有多少种删除元素后可以变成空串的方法很明显是一种,就是删除所有元素。(dp[0][0]也满足)
dp数组的递推公式:注意这里dp数组的含义是方法数!!!
一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。
一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。
dp数组的遍历顺序:正序遍历
uint64_t 是 C/C++ 语言中的整数数据类型,它表示无符号的 64 位整数。在标准头文件
<cstdint>
中定义,并且可用于确保在不同平台上具有相同大小的无符号 64 位整数。uint64_t
类型通常用于需要大范围整数值的情况,例如处理大量数据或需要确保数值不为负的情况。
3.两个字符串的删除操作
代码随想录 (programmercarl.com)
代码: (正面思考。去模拟删除过程)
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1,0));// dp[i][j] dp[i][j]表示s中下标为0~i-1的字串 和 t中下标为0~j-1的子串 相同的最小步数for(int i = 0; i <= word1.size(); i++){dp[i][0] = i;}for(int j = 0; j <= word2.size(); j++){dp[0][j] = j;}// 递推for(int i = 1; i <= word1.size();i++){for(int j = 1; j <= word2.size(); j++){if(word1[i - 1] == word2[j - 1]){dp[i][j] = dp[i - 1][j - 1]; // 新加的两个元素本来就相同,不需要做任何操作}else{dp[i][j] = min(dp[i - 1][j] + 1,min(dp[i][j - 1] + 1,dp[i - 1][j - 1] + 2));// 新加进来的元素不同,要不删掉其中一个,要不两个都删了}}}return dp[word1.size()][word2.size()];}
};
思路:
dp数组的含义:dp[i][j] dp[i][j]表示s中下标为0~i-1的字串 和 t中下标为0~j-1的子串 相同的最小步数
dp数组的递推公式:新加的两个元素本来就相同,不需要做任何操作 dp[i][j] = dp[i - 1][j - 1];新加的两个两个元素不同,要不删掉其中一个,要不两个都删了。dp[i][j] = min(dp[i - 1][j] + 1,min(dp[i][j - 1] + 1,dp[i - 1][j - 1] + 2))
dp数组的初始化:按照定义初始化就好了。
dp数组的遍历顺序:正序遍历
代码:(反面来思考。用最少的操作剩下的子序列,不就是最长公共子序列吗?只要做一下减法就好了)
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1,0));// dp[i][j]表示dp[i][j]表示下标为0~i-1和0~j-1字符串的最长公共子序列的长度。for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i - 1] == word2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}}}return word1.size() + word2.size() - 2 * dp[word1.size()][word2.size()];}
};
4.编辑距离
代码随想录 (programmercarl.com)
代码:
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1,0));// dp[i][j] dp[i][j]表示s中下标为0~i-1的字串 和 t中下标为0~j-1的子串 相同的最小操作数// 这道题和上一道的区别就是替换用到操作数其实是会变少的。// 添加和删除元素的所用的操作数都是一样的。for(int i = 0; i <= word1.size(); i++){dp[i][0] = i;}for(int j = 0; j <= word2.size(); j++){dp[0][j] = j;}for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i - 1] == word2[j - 1]){dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = min(dp[i][j - 1] + 1,min(dp[i - 1][j] + 1,dp[i - 1][j - 1] + 1));// 区别就在这里 dp[i - 1][j - 1] + 1就表示替换 上一题我们这里是加2,因为只能用删除}}}return dp[word1.size()][word2.size()];}
};
思路:
因为添加和删除,其实相对的操作次数是相同的。
这一道题和上一题唯一的区别就是 这里的替换表达式是dp[i - 1][j - 1] + 1 ;而上一题我们只能用删除,所以这里是dp[i - 1][j - 1] + 2。替换所用的操作数少了1.。
这篇关于代码随想录训练营Day 58|力扣392.判断子序列、115不同的子序列、583两个字符串的删除操作、72编辑距离的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!