Is Subsequence
给你两个字符串，s 和 t。如果可以删除 t 中的一些字母（也可以不删除），使其变成 s，并且剩余字母的顺序保持不变，则返回 true，否则返回 false。例如，ace 是 abcde 的子序列，但 aec 不是。
函数
- sstring
- 要查找的字符串
- tstring
- 要从中删除字母的字符串
- 返回值boolean
- 如果可以按顺序在 t 中读取 s，中间可能有间隔，则为 true
约束条件
1 ≤ s.length ≤ 3 × 1041 ≤ t.length ≤ 5 × 104s和t只包含小写英文字母。
示例
- 输入
- s = "ace"t = "abcde"
- 输出
- true
- 解释
- 从
abcde中删除b和d后，剩下ace，顺序不变。
- 输入
- s = "aec"t = "abcde"
- 输出
- false
- 解释
t包含全部三个字母，但唯一的c位于唯一的e前面。使用索引 4 处的e后，它右边就没有剩余的c了。
- 输入
- s = "moon"t = "monsoon"
- 输出
- true
- 解释
- 使用
monsoon中索引 0 处的m、索引 1 和 4 处的o，以及索引 6 处的n。中间的字母会被删除。
进阶
如果 t 保持不变，而你要将一百万个字符串 s 与它逐一比较，该如何预处理 t，让每次比较都比读取 t 的全部内容更快？
提示
逐个打开提示，每个都会多透露一点。
看看
s的第一个字母。在t中，你应该使用它的哪一个副本？使用最早的副本。选择较晚的副本只会让
t留给s剩余部分的内容更少，所以选择最早的副本不会更差。在
s和t中各保留一个索引。逐个遍历t中的字母，每次匹配时都将s中的索引向前移动一步，并在最后检查它是否到达了s的末尾。
题解
子序列可以跳过 t 中任意位置的字母，因此你可能会想尝试 s 的许多种放置方式。其实没必要：让 s 中的每个字母都匹配它能出现的最早位置，结果不会比其他选择更差，所以用两个指针从左到右遍历一遍就能判断。
前缀动态规划
结果正确，但无法在最大的测试中运行完毕
思路
令 dp[i][j] 表示 s 的前 i 个字母能否匹配 t 的前 j 个字母。如果不包含 t[j-1] 时它们已经匹配，或者 s[i-1] 等于 t[j-1] 且前 i-1 个字母能匹配 t[:j-1]，那么它们就能匹配。空前缀可以匹配任意位置，而第 i 行只读取第 i-1 行，因此使用长度为 m+1 的两行就足够了。
该表会填满每个单元格：当 s 有 25,000 个字母，t 有 50,000 个字母时，共有 1.25 × 10^9 个单元格。
算法
- 创建一行包含
m+1个值的prev，并将它们全部设为true：空s可以匹配t的每个前缀。 - 对于从 1 到
n的每个i，创建一行cur，并令cur[0] = false。 - 对于从 1 到
m的每个j，将cur[j]设为cur[j-1]；如果s[i-1]等于t[j-1]，则将其设为prev[j-1]。 - 用
cur替换prev。 - 返回
prev[m]。
def isSubsequence(s, t):
n, m = len(s), len(t)
# prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
prev = [True] * (m + 1)
for i in range(1, n + 1):
cur = [False] * (m + 1)
for j in range(1, m + 1):
cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
prev = cur
return prev[m]使用贪心匹配的双指针
思路
用指针 i 指向你需要的 s 中下一个字母，并取你在 t 中遇到的第一个匹配项。这样选择是安全的。如果某个有效放置使用了 s[i] 的更靠后的匹配项，那么换成最早的匹配项仍能保持顺序，并为 s 的其余部分留下更多 t。因此，只要存在有效放置，贪心策略就能找到它。
循环最多读取 t 中的每个字母一次，并保留两个索引：时间复杂度为 O(n + m)，空间复杂度为 O(1)。
算法
- 为
s设置i = 0，为t设置j = 0。 - 当两个索引都在各自的字符串范围内时，比较
s[i]和t[j]。 - 如果它们相等，就增加
i。 - 无论如何都增加
j。 - 返回
i是否等于s的长度。
def isSubsequence(s, t):
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
易错点和边界情况
- 在
t的任意位置搜索s中的每个字母，而不是从上一次匹配的位置之后开始搜索。这样会把aec判定为abcde的子序列。 - 把同一个字母用两次。
noon不是moon的子序列：它唯一的n位于索引 3，不能同时作为第一个和最后一个字母。 - 返回
j是否到达了t的末尾。无论是否找到s，循环往往都会在那里结束；只有i能告诉你结果。 - 当
t用完时没有停止。对于abc和ab，必须返回false。 - 在
i到达s的末尾后读取s[i]。在 Python 或 Java 中，这样读取会抛出异常，所以比较前要先检查i。
常见问题3
判断子序列的时间复杂度是多少？
双指针解法的运行时间为 O(n + m)，其中 n 和 m 分别是 s 和 t 的长度，额外占用 O(1) 的内存。循环最多执行 m 步后停止。前缀表需要 O(n × m) 的时间。
“Is Subsequence”与最长公共子序列有什么关系？
当 s 的所有字符都包含在它们的最长公共子序列中，且该子序列的长度为 n 时，s 才是 t 的子序列。第一种方法中的前缀表就是为那个问题构建的。这里你只需要判断 s 的所有字符是否都能匹配上，因此贪心遍历就足够了。
子序列和子字符串有什么区别？
子字符串是由连续字母组成的片段，而子序列可以跳过一些字母，只要顺序保持不变即可。ace 是 abcde 的子序列，但不是它的子字符串。每个子字符串都是子序列，但反过来不一定成立。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isSubsequence(s, t):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "ace" t = "abcde"
预期输出
true