难度: Easy
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4运行时间: 15 ms
内存: 16.0 MB
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
if s == '':
return True
for j in t:
if j == s[i]:
i += 1
if i == len(s):
return True
return False
该题解采用了双指针的思路。用两个指针i和j分别指向字符串s和t的开头。遍历字符串t，如果当前字符t[j]等于s[i]，则i向右移动。最后判断i是否等于s的长度，如果等于则说明s是t的子序列，否则不是。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
if s == '': # 如果s为空串，直接返回True
return True
for j in t: # 遍历字符串t
if j == s[i]: # 如果当前字符等于s[i]
i += 1 # i右移
if i == len(s): # 如果i等于s的长度，说明s已经遍历完毕，是t的子序列
return True
return False # 遍历完t后i仍不等于s的长度，说明s不是t的子序列
当面对大量的S输入时，单个查询的效率变得尤为重要。当前的双指针逻辑对每个查询都需要遍历整个字符串T，时间复杂度为O(n)，其中n是T的长度。如果S非常多，这种方法会导致总的时间复杂度非常高。因此，可以考虑预处理T，例如使用哈希表或索引数组记录字符在T中的位置，以实现更快的查询，从而优化对大量S输入的处理。
在定义上，空字符串是任何字符串的子序列，因为没有字符需要匹配。因此，不管T是什么，空字符串s总是T的子序列。这里考虑了所有可能的场景，只要s是空的，无论t的内容如何，都应该返回True。
如果s的长度大于t的长度，理论上s不可能是t的子序列，因为没有足够的空间在t中按序容纳所有s的字符。因此，可以在开始遍历之前添加一个判断：如果s的长度大于t的长度，直接返回False，这样可以提高算法的效率，避免不必要的遍历。
是的，该算法会返回false。因为算法不仅检查t中是否存在s的所有字符，还检查这些字符是否以相同的顺序出现。如果顺序不同，即使t包含s的所有字符，算法也不会认为s是t的子序列。