力扣 392. 判断子序列

本文主要是介绍力扣 392. 判断子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：https://leetcode.cn/problems/is-subsequence/description/

C++题解1：在t中按顺序一个一个寻找s的元素。

class Solution {
public:bool isSubsequence(string s, string t) {bool flg = false;int m = s.size(), n = t.size();if(m == 0) return true;int j = 0;for(int i = 0; i < n; i++){if(s[j] == t[i]) {j++;if(j == m){flg = true; break;}}}return flg;}
};

C++题解2（来源代码随想录）：动态规划。虽然这样复杂好多，但是原网址说是为了后续的学习打下基础。

1. 确定dp数组（dp table）以及下标的含义。dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
2. 确定递推公式。在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

• if (s[i - 1] == t[j - 1])：t中找到了一个字符在s中也出现了
• if (s[i - 1] != t[j - 1])：相当于t要删除元素，继续匹配

class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size(), n = t.size();if(m == 0) return true;vector<vector<int>> dp(m+1, vector<int>(n+1, 0));for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; 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[m][n] == m) return true;else return false;}
};

这篇关于力扣 392. 判断子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---