链接：https://leetcode.cn/problems/is-subsequence/solution/-by-xun-ge-v-c0pu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。?
题目
?
示例
?
思路
方法一
- 确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。
- 确定递推公式
在确定递推公式的时候，首先要考虑如下两种操作，整理如下：
- if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出现了
- if (s[i - 1] != t[j - 1])
- 相当于t要删除元素，继续匹配
if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）
if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
- dp数组如何初始化
从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
方法二
对于思考题的思路
这种类似对同一个长字符串做很多次匹配的 ，可以像 KMP 算法一样，先用一些时间将长字符串中的数据 提取出来，磨刀不误砍柴功。有了提取好的数据，就可以快速的进行匹配。
- 1.我们需要提取什么样的数据
这道题其实是贪心算法，上面的整个算法很简单，容易理解（是因为人都是贪心的吗 233）。 这里需要的数据就是匹配到某一点时 待匹配的字符在长字符串中 下一次 出现的位置。
所以我们前期多做一点工作，将长字符串研究透彻，假如长字符串的长度为 nn，建立一个 n * 26 大小的矩阵，表示每个位置上26个字符下一次出现的位置。实现如下：
? ? int dp[n][26];
? ? memset(dp, 0, sizeof(dp));
? ? for (char c = 'a'; c <= 'z'; c++) {
? ? int nextPos = -1; //表示接下来再不会出现该字符
? ? for (int i = len2 - 1; i>= 0; i--) { ?//为了获得下一个字符的位置，要从后往前
? ? ? ? dp[i][c - 'a'] = nextPos;
? ? ? ? if (t[i] == c)
? ? ? ? ? ? nextPos = i;
? ? }- 2.数据的利用
对于要匹配的短字符串，遍历每一个字符，不断地寻找该字符在长字符串中的位置，然后将位置更新，寻找下一个字符，相当于在长字符串上“跳跃”。
如果下一个位置为 -1，表示长字符串再没有该字符了，返回 false 即可。
如果能正常遍历完毕，则表示可行，返回 true
? ? int index = 0;
? ? for (int i = 0; i < lens; i++) {
? ? ? ? index = dp[index][s[i] - 'a'];
? ? ? ? if (index == -1)
? ? ? ? ? ? return false;
? ? }
? ? return true;- 3.需要注意的一点
对于 "abc" 在 "ahbgdc" 上匹配的时候，由于长字符串第一个 a 的下一个出现 a 的位置为 -1（不出现），会导致一个 bug。
所以在生成数组时在长字符串前插入一个空字符(相当于哨兵)即可。
代码
#define MAX(a, b) ((a) > (b) ? (a) : (b))
bool isSubsequence(char * s, char * t){
int lens = strlen(s);
int lent = strlen(t);
int dp[lens+1][lent+1];
memset(dp, 0, sizeof(dp));//初始化
int max = 0;
for(int i = 1; i <= lens; i++)
{
for(int j = 1; j <= lent; j++)//枚举数组元素
{
if(s[i-1] == t[j-1])//相同元素 + 1
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else//不需要，保存最大上一个相同值
{
dp[i][j] = dp[i][j-1];
}
max = MAX(max, dp[i][j]);
}
}
return max == lens ? 1 : 0;
}
作者：xun-ge-v
链接：https://leetcode.cn/problems/is-subsequence/solution/-by-xun-ge-v-c0pu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。