国外一直小猫做图标的网站,佛山中谦建设网站,做涂鸦的网站,淘宝电商设计一、leetcode第392题
本题要求判断s是否为t的子序列#xff0c;因此设置dp数组#xff0c;dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数#xff0c;可得递推公式是通过s[i-1]和t[j-1]是否相等区分。
具体代码如下#xff1a;
class Solution {
publ…一、leetcode第392题
本题要求判断s是否为t的子序列因此设置dp数组dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数可得递推公式是通过s[i-1]和t[j-1]是否相等区分。
具体代码如下
class Solution {
public:bool isSubsequence(string s, string t) {vectorvectorintdp(s.length()1,vectorint(t.length()1,0));for(int i1;is.length();i){for(int j1;jt.length();j){if(s[i-1]t[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]dp[i][j-1];}}}if(dp[s.length()][t.length()]s.length()){return true;}return false;}
};
二、leetcode第115题
本题要求s的子串与t相等的个数因此设置dp数组其中dp[i][j]的含义是i-1为下标的子串中包含j-1为下标的子串的个数根据s[i-1]和t[j-1]是否相等来写递推公式相等时递推公式dp[i][j]由dp[i-1][j-1]考虑s[i-1]和dp[i-1][j]不考虑s[i-1]构成不相等时则等于不考虑s[i-1]时的递推式。
具体代码如下
class Solution {
public:int numDistinct(string s, string t) {vectorvectoruint64_tdp(s.length()1,vectoruint64_t(t.length()1));for(int i0;is.length();i){dp[i][0]1;}for(int j1;jt.length();j){dp[0][j]0;}for(int i1;is.length();i){for(int j1;jt.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()];}
};
