设计一个算法，判断字符串 s2 是否是字符串 s1 的子序列。例如，s1='abcde'，s2='ace'，返回 true；s1='abcde'，s2='aec'，返回 false。请分析算法的时间复杂度和空间复杂度。
答案
1) 【一句话结论】使用双指针法，通过遍历s1和s2，判断s2的字符能否按顺序匹配s1中的字符，若s2全部匹配则返回true，否则false。
2) 【原理/概念讲解】首先明确“子序列”的定义：字符串s2是s1的子序列，当且仅当存在一个从s1中按顺序选取字符的序列，能组成s2。例如s1='abcde'，s2='ace'，选取a（位置0）、c（位置2）、e（位置4）即可。双指针法的核心是维护两个指针i（指向s1）和j（指向s2），初始都为0。遍历s1时，若s1[i] == s2[j]，则j++（匹配成功，继续检查s2的下一个字符）；无论是否匹配，i都++（继续检查s1的下一个字符）。当j到达s2的末尾时，说明s2的所有字符都已按顺序匹配，返回true；遍历结束后j未到末尾，返回false。类比：就像找s2在s1中的“路径”，指针i像在s1中前进，指针j记录s2已匹配的位置，只要s1的字符能“接住”s2的当前字符，j就前进，直到j走完s2。
3) 【对比与适用场景】
| 方法 | 定义 | 时间复杂度 | 空间复杂度 | 使用场景 |
|---|---|---|---|---|
| 双指针法 | 遍历s1和s2，逐个字符匹配 | O(n)（n为s1长度） | O(1) | 大多数子序列问题，尤其是s1和s2长度较大时 |
| 暴力匹配（双循环） | 两重循环，外层遍历s1，内层遍历s2，逐个字符比较 | O(n*m)（n为s1长度，m为s2长度） | O(1) | s1和s2较短时，或理解基础逻辑 |
| KMP（扩展） | 预处理s2的next数组，匹配时跳过已匹配部分 | O(n+m) | O(m) | 需要高效处理多个子序列查询 |
注意点：双指针法适用于单次查询，KMP适用于多次查询。
4) 【示例】以s1='abcde'，s2='ace'为例，伪代码：
i=0, j=0;
while i < len(s1) and j < len(s2):
if s1[i] == s2[j]:
j += 1;
i += 1;
if j == len(s2):
return true;
else:
return false;
对于s1='abcde', s2='aec'，i=0时s1[0]='a'匹配s2[0]='a'，j=1；i=1时s1[1]='b'不匹配，i=2，s1[2]='c'不匹配s2[1]='e'，i=3，s1[3]='d'不匹配，i=4，s1[4]='e'匹配s2[1]='e'，但j此时是1 < 3，返回false。
5) 【面试口播版答案】面试官您好，这个问题是判断字符串s2是否是s1的子序列。我的思路是使用双指针法，具体来说，我们维护两个指针i和j，分别指向s1和s2的起始位置。然后遍历s1，当s1[i]等于s2[j]时，j指针向前移动一位，表示当前字符匹配成功；无论是否匹配，i指针都会向前移动一位。当j指针移动到s2的末尾时，说明s2的所有字符都按顺序出现在s1中，此时返回true；如果遍历结束后j还没到s2的末尾，就返回false。比如s1='abcde'，s2='ace'，i从0开始，i=0时'a'匹配s2的'a'，j变成1；i=1时'b'不匹配，i变成2，s1[2]='c'匹配s2[1]='c'，j变成2；i=3时'd'不匹配，i=4，s1[4]='e'匹配s2[2]='e'，j变成3，此时j等于s2长度3，返回true。而s2='aec'时，i=0时'a'匹配s2[0]='a'，j=1；i=1时'b'不匹配，i=2，s1[2]='c'不匹配s2[1]='e'，i=3，s1[3]='d'不匹配，i=4，s1[4]='e'匹配s2[1]='e'，但j此时是1，还没到3，所以返回false。时间复杂度是O(n)，因为每个字符最多遍历一次；空间复杂度是O(1)，只用了两个指针。
6) 【追问清单】
- 问：时间复杂度分析是否正确？比如是否考虑了空字符串的情况？
回答要点：空字符串的情况，s2为空时直接返回true（因为空字符串是任何字符串的子序列）；s1为空且s2不为空时返回false，这些边界情况不影响整体O(n)的时间复杂度。 - 问：空间复杂度是否可以优化？比如有没有用额外数组的方法？
回答要点：双指针法已经是O(1)空间复杂度，额外数组的方法（比如预处理s2的字符位置）会占用O(m)空间，对于单次查询来说，双指针更优。 - 问：如果s1和s2都很长，比如10^5长度，这个方法是否高效？
回答要点：是的，双指针法的时间复杂度是O(n)，对于10^5长度的字符串，单次遍历是高效的，不会超时。 - 问：有没有其他方法，比如KMP？为什么这里用双指针？
回答要点：KMP适用于需要多次查询子序列的情况，而本题是单次查询，双指针更简单高效，且时间复杂度相同（O(n)），但实现更简单。 - 问：如果s1和s2包含重复字符，这个方法是否仍然适用？
回答要点：适用，因为双指针只关心字符是否按顺序出现，不关心重复次数，只要顺序匹配即可。
7) 【常见坑/雷区】
- 忽略空字符串的情况：比如s1为空，s2不为空时返回true，这是错误的，因为空字符串不是非空字符串的子序列。
- 时间复杂度误判：认为双指针法是O(n*m)，混淆了双指针和暴力匹配。
- 空间复杂度错误：认为需要额外存储s2的字符位置，导致空间复杂度不是O(1)。
- 顺序错误：先移动j指针再移动i指针，导致逻辑错误，比如s1='abcde'，s2='ab'，i=0时'a'匹配，j=1，i=1时'b'匹配，j=2，此时j等于s2长度2，返回true，但如果顺序错误，可能会漏掉匹配。
- 边界情况处理不当：比如s2为空时，直接返回true，但有些面试官可能希望明确说明，不过不影响核心逻辑。