链接：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。