1 算法题 ：检查一个字符串是否是某个字符串的子序列
1.1 题目含义
这个题目要求检查一个字符串是否是另一个字符串的子序列。子序列指的是一个字符串可以通过删除原字符串中的某些字符（也可以不删除）但不改变剩下字符的顺序而得到。例如，字符串 “ace” 是 “abcde” 的一个子序列，因为可以删除 ‘b’ 和 ‘d’ 来得到 “ace”。但是，字符串 “aec” 不是 “abcde” 的子序列，因为虽然 “a”, “e” 和 “c” 都存在于 “abcde” 中，但它们的相对顺序在 “aec” 中改变了。
1.2 示例
示例 1:
输入： 主字符串：“abcde”，子字符串： “ace”
输出： true
解释： “ace” 是 “abcde” 的一个子序列，因为可以删除 ‘b’ 和 ‘d’ 来得到 “ace”。
示例 2:
输入： 主字符串：“hello”，子字符串： “ll”
输出： true
解释： “ll” 是 “hello” 的一个子序列，因为可以删除 ‘h’, ‘e’, ‘o’ 来得到 “ll”。
示例 3:
输入： 主字符串：“abcde”，子字符串： “aec”
输出： false
解释： “aec” 不是 “abcde” 的一个子序列，因为虽然 “a”, “e” 和 “c” 都存在于 “abcde” 中，但它们的相对顺序在 “aec” 中改变了。
2 解题思路
对于检查一个字符串是否是另一个字符串的子序列的问题，可以使用双指针法来解决。具体步骤如下：
（1）初始化两个指针，一个指向主字符串的开始位置，另一个指向子字符串的开始位置。
（2）开始一个循环，该循环会一直执行直到子字符串的指针遍历完整个子字符串，或者主字符串的指针遍历完整个主字符串。
（3）在循环中，比较两个指针当前所指向的字符是否相等：
- 如果相等，说明找到了子字符串的一个字符，将子字符串的指针向前移动一位。
- 如果不相等，说明当前主字符串的字符不是子字符串所需要的，因此将主字符串的指针向前移动一位。
（4）当子字符串的指针遍历完整个子字符串时，说明子字符串中的每一个字符都在主字符串中按顺序找到了，因此子字符串是主字符串的子序列，返回 true。
（5）如果主字符串的指针先遍历完整个主字符串，说明在主字符串中无法按顺序找到子字符串的所有字符，因此子字符串不是主字符串的子序列，返回 false。
这个算法的时间复杂度是 O(n+m)，其中 n 和 m 分别是主字符串和子字符串的长度。因为我们最多需要遍历主字符串和子字符串各一次。空间复杂度是 O(1)，因为这里只使用了常数级别的额外空间来存储指针。
3 算法实现代码
3.1 使用双指针法
如下为算法实现代码：
#include <iostream>
#include <string>
class Solution
{
public:
bool isSubsequence(std::string s, std::string t) {
int i = 0; // 指向主字符串s的指针
int j = 0; // 指向子字符串t的指针
// 当子字符串t的指针j没有遍历完时，继续循环
while (j < t.size()) {
// 如果主字符串s的指针i没有遍历完，并且当前字符匹配
if (i < s.size() && s[i] == t[j]) {
// 两个指针都向前移动一位
i++;
j++;
}
else {
// 如果不匹配或者主字符串s已经遍历完，则只移动主字符串的指针i
i++;
}
}
// 如果子字符串t的指针j遍历完整个子字符串，说明是子序列
return j == t.size();
}
};
在这段代码中，isSubsequence 函数实现了上述解题思路。它接收两个字符串 s 和 t，分别代表主字符串和子字符串。函数内部通过两个指针 i 和 j 来遍历字符串，并根据比较结果移动指针。如果最后 j 等于 t.size()，则说明子字符串 t 是主字符串 s 的子序列，函数返回 true；否则返回 false。
调用上面的算法，并得到输出：
int main()
{
Solution s;
std::string str = "abcde";
std::string sub = "ace";
if (s.isSubsequence(str, sub)) {
std::cout << sub << " is a subsequence of " << str << std::endl;
}
else {
std::cout << sub << " is not a subsequence of " << str << std::endl;
}
return 0;
}
上面代码的输出为：
ace is a subsequence of abcde
3.2 使用动态规划法
除了双指针法之外，另一种检查子序列的解题思路是使用动态规划或者一个简化的方法，即遍历主字符串并在每次找到与子字符串当前字符匹配时，更新子字符串的索引。这种方法不需要使用额外的空间来存储状态，因此空间复杂度更低。
如下为算法实现代码：
#include <iostream>
#include <string>
class Solution
{
public:
bool isSubsequence(std::string s, std::string t) {
int j = 0; // 指向子字符串t的索引
for (char c : s) { // 遍历主字符串s
if (j < t.size() && c == t[j]) {
// 找到匹配的字符，子字符串索引加一
j++;
}
}
// 如果子字符串的所有字符都找到了，则返回true
return j == t.size();
}
};
在这个实现中，只需要一个索引 j 来跟踪子字符串 t 的当前位置。遍历主字符串 s 中的每个字符，如果当前字符与 t[j] 相等，就将 j 增加 1。最后，如果 j 等于 t.size()，说明已经在 s 中按顺序找到了 t 的所有字符，因此 t 是 s 的子序列。
这种方法同样具有 O(n+m) 的时间复杂度，其中 n 和 m 分别是主字符串和子字符串的长度，因为每个字符最多被遍历一次。空间复杂度是 O(1)，因为只使用了常数级别的额外空间来存储索引 j。
4 测试用例
以下是针对上面算法的测试用例，基本覆盖了各种情况：
（1）基础测试用例
输入：主字符串 “abcde”，子字符串 “ace”
输出：true
说明：子字符串 “ace” 是主字符串 “abcde” 的子序列，因为字符 ‘a’、‘c’ 和 ‘e’ 在主字符串中按顺序出现。
（2）子字符串为空字符串的测试用例
输入：主字符串 “abcde”，子字符串 “”
输出：true
说明：空字符串是任何字符串的子序列。
（3）主字符串为空字符串的测试用例
输入：主字符串 “”，子字符串 “abc”
输出：false
说明：非空字符串不可能是空字符串的子序列。
（4）子字符串与主字符串相同的测试用例
输入：主字符串 “abcde”，子字符串 “abcde”
输出：true
说明：子字符串 “abcde” 是主字符串 “abcde” 的子序列，因为它们完全相同。
（5）子字符串为主字符串的前缀的测试用例
输入：主字符串 “abcde”，子字符串 “abc”
输出：true
说明：子字符串 “abc” 是主字符串 “abcde” 的子序列，因为 “abc” 是 “abcde” 的前缀。
（6）子字符串为主字符串的后缀的测试用例
输入：主字符串 “abcde”，子字符串 “cde”
输出：true
说明：子字符串 “cde” 是主字符串 “abcde” 的子序列，尽管 “cde” 是 “abcde” 的后缀，但子序列的定义并不要求字符连续。
（7）子字符串包含主字符串未出现的字符的测试用例
输入：主字符串 “abcde”，子字符串 “acfx”
输出：false
说明：子字符串 “acfx” 中的 ‘f’ 不在主字符串 “abcde” 中，因此 “acfx” 不是 “abcde” 的子序列。
（8）子字符串字符顺序与主字符串不同的测试用例
输入：主字符串 “abcde”，子字符串 “ecba”
输出：false
说明：尽管子字符串 “ecba” 中的字符都在主字符串 “abcde” 中，但它们的顺序不匹配，因此 “ecba” 不是 “abcde” 的子序列。
（9）主字符串和子字符串都较长的测试用例
输入：主字符串 “abcdefghijklmnopqrstuvwxyz”，子字符串 “acegikmoqsuwy”
输出：true
说明：子字符串 “acegikmoqsuwy” 中的字符都在主字符串 “abcdefghijklmnopqrstuvwxyz” 中按顺序出现，尽管它们之间有其他字符。
（10）主字符串和子字符串都包含重复字符的测试用例
输入：主字符串 “aabbbcc”, 子字符串 “abbc”
输出：true
说明：即使主字符串 “aabbbcc” 中包含重复字符，子字符串 “abbc” 仍然是它的子序列，因为可以找到按顺序出现的 ‘a’、‘b’ 、‘b’ 和 ‘c’。