Shouyu

Appearance

判断子序列 ​

题目描述 ​

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

题目链接：https://leetcode.cn/problems/is-subsequence

文章讲解：https://programmercarl.com/0392.判断子序列.html

思路 ​

因为子序列可以删除原字符串中的一些字符，因此我们可以双指针法，同时比较 s 和 t 字符，然后不同时，t 字符串跳过字符。

这样，如果 s 遍历完所有字符到达 s.size() 那么 s 是 t 的子序列，如果没有遍历完则不是。

可以考虑动态规划。

和 最长公共子序列 类似的是，那道题是两个字符串中的子序列，这道题改为一个。那道题求长度，这道题只要求是否是子序列。

转化一下就可以是 s 和 t 的最长公共子序列的最长长度有没有到达 s 的长度。

动规五部曲 ​

1、dp 数组及下标含义 ​

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

2、递推公式 ​

两种情况：

  • if (s[i - 1] == t[j - 1])
    • t 中找到了一个字符在 s 中也出现了，dp[i][j] = dp[i-1][j-1] + 1
  • if (s[i - 1] != t[j - 1])
    • 相当于 t 要删除元素，继续匹配，那么就是继续看 t 的前一个数值与 s 比较结果。因为同样作为子序列，t 能删除，而 s 却不能删除元素。 dp[i][j] = dp[i][j-1];
3、初始化 ​

从递推公式上看dp[0][0] dp[i][0] 一定需要初始化。我们从i = 1开始遍历，就能够直接定义以 i = 0结尾的子序列了。初始化为 0 就可以了，这样 i =1时 dp[1] 是计算正确的，后续就也正确率

4、确定遍历顺序 ​

i j 依赖于左边和左上方，因此 从上到下 从左到右遍历即可。

5、举例推导 ​

输入：s = "abc", t = "ahbgdc"，dp状态转移图如下：

392.判断子序列2

最后如果 dp[s.size()][t.size()] == s.size() 就说明s 和 t 的最长公共子序列的最长长度是 s 的长度 ，即 s 是 t 的子序列

代码实现 ​

C++
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;
}