[LeetCode]Is Subsequence

双指针即可解决，即使T中存在多个S子序列我们依然可以找到第一个。假设S长M，T长N，时间复杂度O(M + N)，常数空间。代码如下：



对于Follow up的问题，当我们用来query的S序列很多个，我们如何优化。一般对于这种问题，我们一般是用某种数据结构对T进行预处理来省下一些时间。我们要保证S是T的子序列的话，对于S中的字符s[i]，其在T中的位置为可能存在多个位置，那么对应每一个字符，我们选择其在T 中的某个位置，我们可以得到一串序列，如果这个序列是递增的，代表S是T的子序列。根据这个思路，我们对T进行预处理，统计每个字符出现的index，存入数组中，这个数组是sorted的，对于每一个字符，我们binary search符合要求的字符（当前数组中大于我们之前找到的index的最小值）。鉴于字符的种类是有限的，假设我们只用字母，时间复杂度为M * log(26) = O(M)。我们节省了要每次扫T的时间，代码如下：