算法训练营day58

题目1：392. 判断子序列 - 力扣（LeetCode）

暴力解法

class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() > t.size()) return false;if(s.size() < t.size()) {swap(s, t);}bool reslut = false;int flag = 0;bool findflag = false;for(int i = 0;i < t.size();i++) {for(;flag < s.size();flag++) {if(s[flag] == t[i]) {flag++;findflag = true;break;}}if(findflag) {findflag = false;}else return false;}return true;}
};

动态规划，其实和之前最长公共子序列一样，只不过最后就是比较以下dp数组的值是否和字符串s的长度相同

class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() > t.size()) return false;vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 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]);// 这里其实 = dp[i][j - 1]就可以                }}}if(dp[s.size()][t.size()] == s.size()) return true;else return false;}
};