392. Is Subsequence


Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Special thanks to @pbrother for adding this problem and creating all test cases.





class Solution {
    bool isSubsequence(string s, string t) {
        int i = 0;
        for (int j = 0; j < t.size() && i < s.size(); ++j) {
            if (s[i] == t[j]) ++i;
        return i == s.size();


题目中的 Follow up 说如果有大量的字符串s,问我们如何进行优化。那么既然字符串t始终保持不变,我们就可以在t上做一些文章。子序列虽然不需要是连着的子串,但是字符之间的顺序是需要的,那么我们可以建立字符串t中的每个字符跟其位置直接的映射,由于t中可能会出现重复字符,所以把相同的字符出现的所有位置按顺序加到一个数组中,所以就是用 HashMap 来建立每个字符和其位置数组之间的映射。然后遍历字符串s中的每个字符,对于每个遍历到的字符c,我们到 HashMap 中的对应的字符数组中去搜索,由于位置数组是有序的,我们使用二分搜索来加快搜索速度,这里需要注意的是,由于子序列是有顺序要求的,所以需要一个变量 pre 来记录当前匹配到t字符串中的位置,对于当前s串中的字符c,即便在t串中存在,但是若其在位置 pre 之前,也是不能匹配的。所以我们可以使用 uppper_bound() 来二分查找第一个大于 pre 的位置,若不存在,直接返回 false,否则将 pre 更新为二分查找的结果并继续循环即可,参见代码如下:



// Follow up
class Solution {
    bool isSubsequence(string s, string t) {
        int pre = -1, n = t.size();
        unordered_map<char, vector<int>> char2pos;
        for (int i = 0; i < n; ++i) char2pos[t[i]].push_back(i);
        for (char c : s) {
            auto it = upper_bound(char2pos[c].begin(), char2pos[c].end(), pre);
            if (it == char2pos[c].end()) return false;
            pre = *it;
        return true;



Number of Matching Subsequences







LeetCode All in One 题目讲解汇总(持续更新中…)

转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com



Venmo 打赏



Help us with donation