本文主要是介绍代码随想录算法训练营第五十四天 | 392.判断子序列,115.不同的子序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
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;}
};
动态规划反而麻烦,但是思想可以过一遍:
(1)dp[ i ][ j ] 表示 s 前 i 个元素与 t 的前 j 个元素的相同子序列的长度;
(2)if( 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) {vector<vector<int>> dp(s.size() + 1, vector<int>(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. 不同的子序列
(1)dp[ i ][ j ] 表示在 s 的前 i 个元素的子序列中出现 t 的前 j 个元素的个数;
(2)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 ];
(3)dp[ i ][ 0 ] = 1;
(4)外层遍历 s,内层遍历 t;
class Solution {
public:int numDistinct(string s, string t) {vector<vector<unsigned long long>> dp(s.size() + 1, vector<unsigned 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()];}
};
这篇关于代码随想录算法训练营第五十四天 | 392.判断子序列,115.不同的子序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!