沧县网站建设公司,站长忽略的观点,成都网站制作公司科蓝,服装做外贸的网站建设目录 392.判断子序列 115.不同的子序列 392.判断子序列 题目链接#xff1a;392. 判断子序列 设 s 的指针#xff0c;遍历 t 的各个元素#xff0c;当 t 与 s 对应元素相同时#xff0c;指针前进#xff1a; class Solution {
public:bool isSubsequence(string s, string… 目录 392.判断子序列 115.不同的子序列 392.判断子序列 题目链接392. 判断子序列 设 s 的指针遍历 t 的各个元素当 t 与 s 对应元素相同时指针前进 class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() 0) return true;int index 0;for(int i 1; i t.size(); i){if(t[i - 1] s[index]){index;}if(index s.size()) return true;}return false;}
}; 动态规划反而麻烦但是思想可以过一遍 1dp[ i ][ j ] 表示 s 前 i 个元素与 t 的前 j 个元素的相同子序列的长度 2if( s[ i - 1 ] t[ i - 1 ] ) dp[ i ][ j ] dp[ i - 1 ][ j - 1 ] 1; else dp[ i ][ j ] dp[ i ][ j - 1 ]; 3设 dp[ 0 ][ 0 ] 0 为空状态 4外层遍历 s 的每个元素内层遍历 t 的每个元素 class Solution {
public:bool isSubsequence(string s, string t) {vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));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] dp[i][j - 1];}}if(dp[s.size()][t.size()] s.size()) return true;return false;}
}; 115.不同的子序列 题目链接115. 不同的子序列 1dp[ i ][ j ] 表示在 s 的前 i 个元素的子序列中出现 t 的前 j 个元素的个数 2if( 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 ]; 3dp[ i ][ 0 ] 1; 4外层遍历 s内层遍历 t class Solution {
public:int numDistinct(string s, string t) {vectorvectorunsigned long long dp(s.size() 1, vectorunsigned long long(t.size() 1, 0));for(int i 0; i s.size(); i) 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];} else {dp[i][j] dp[i - 1][j];}}}return dp[s.size()][t.size()];}
};
