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

题目

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

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

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

进阶：

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

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

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

提示

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，所以初始化的时候需要将长度加一。

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就可以了。

代码

完整代码如下

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的子序列。

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