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?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
这道题算比较简单的一种，我们可以用两个指针分别指向字符串s和t，然后如果字符相等，则i和j自增1，反之只有j自增1，最后看i是否等于s的长度，等于说明s已经遍历完了，而且字符都有在t中出现过，参见代码如下：
解法一：
class Solution {
public:
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 {
public:
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
参考资料：
https://leetcode.com/problems/is-subsequence/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
