距离上次更新本文已经过去了 248 天，文章部分内容可能已经过时，请注意甄别

leetcode 刷题笔记 - 392. 判断子序列

题目

https://leetcode.cn/problems/is-subsequence/description/

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

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

进阶：

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

plaintext
1
2
3
4
5
6
7
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false

提示

plaintext
1
2
3
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

思路一：动态规划

说明

还是用动态规划的思路，本题其实可以借鉴 1143. 最长公共子序列的思路，我们需要判断 s 是否为 t 的子序列，本质上就是判断 s 和 t 是否有公共子序列，且 s 本身就是 s 和 t 的最长公共子序列。

首先是定义 dp 数组，用一个二维数组来表示：dp[i][j] 代表 s 字符串 i-1 和 t 字符串中 j-1 的公共子序列长度为 dp[i][j]。因为是 i-1 和 j-1，所以初始化的时候需要将长度加一。

cpp
1
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

最终我们得到的 dp[s.size()][t.size()]，就是 s 和 t 的公共子序列长度，这个长度应该等于 s 的长度，否则代表 s 不是 t 的子序列。

然后是定义递推公式，分为两种情况

  1. s[i-1]==t[j-1]，代表子序列可以扩张，即 dp[i][j] = dp[i-1][j-1]+1，含义是两个字符串中各上一位的公共子序列长度加一；
  2. s[i-1]!=t[j-1]，代表子序列不能扩张，此时应该沿用 “上一次的结果”，注意这里和 1143 题目就有区别了，我们需要判断 s 是否为 t 的子序列，则只能从 t 中删除元素来匹配 s，所以只能是 dp[i][j] = dp[i][j-1]；

确定了递推公式，根据递推公式可知当前的 dp[i][j] 依赖于 i-1 和 j-1，所以必须从小到大遍历进行推导。因为我们 dp 数组的含义使用了 i-1 和 j-1，所以并不需要对 dp 数组的第 0 列和第 0 行进行单独初始化操作，构造函数里面统一初始化为全 0 就可以了。

代码

完整代码如下

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isSubsequence(string s, string t) {
        // s更长肯定不会是t的子序列
        if (s.size() > t.size()) {
            return false;
        }
        // dp[i][j]表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        // 两种递推的情况
        //  1.当前s和t相等，代表相同子序列长度可以扩张 dp[i][j] = dp[i-1][j-1]+1;
        //  2.当前s和t不相等，相同子序列长度不可扩张，过渡于上一个
        //          如果是普通题目，“上一个”分为两种情况 dp[i-1][j] 和
        //          dp[i][j-1]
        //          但是本题判断s是否为t的子序列，所以我们不能从s中删除元素，只能从t中删除元素
        //          所以只能使用 dp[i][j-1]
        //          代表从t中删除一个元素（删除的其实就是当前元素j-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] = dp[i][j - 1];
                }
            }
        }
        // 如果t中包含s，那么最终得到的相同子序列长度应该是s.size()
        return dp[s.size()][t.size()] == s.size();
    }
};

空间复杂度和时间复杂度是 O(N^2)

image.png

思路二：直接遍历

这道题限制的条件很简单，s 是否为 t 的子序列本质上是 s 中的每个字符是否能按顺序的在 t 中出现。

那么我们只需要从头开始遍历 t 字符串，匹配上一个 s 中的字符后，就开始匹配下一个 s 中的字符，直到 t 字符串遍历完毕。

此时如果 s 字符串中已遍历的部分是 s 字符串的长度，那么就代表 s 是 t 的子序列。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isSubsequence(string s, string t) {
        // s必须长度小于等于t才有可能是t的子序列
        if (s.size() > t.size()) {
            return false;
        }
        // 直接遍历t字符串，判断s中的字符是否在t中按顺序出现了
        int index = 0;
        for (auto& c : t) {
            if (c == s[index]) {
                index++;
            }
        }
        // 如果最终index是s的长度，代表s被完整遍历了，即s是t的子序列
        return index == s.size();
    }
};

空间复杂度是 O(1)，时间复杂度是 O(N)。

image.png