动态规划（2）判断子序列

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1: s = “abc”, t = “ahbgdc” 返回 true.

示例 2: s = “axc”, t = “ahbgdc” 返回 false.

后续挑战 : 如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解题思路

逻辑分析：

1. 子问题 在该问题中，子问题为s字符串中的每个字符与t串的匹配关系，即可划分为n = len(s)个子问题。

2. 转移方程 遍历s字符串，在t字符串中寻找相应的字符，当寻找到了一个s中的字符时即意味着解决了一个子问题，当所有s字符串中的所有字符都找到了的时候（即完成寻找时，寻找的次数小于等于t字符串的长度），可以认为s字符串为t字符串的子串。

代码

class Solution: def isSubsequence(self, s: str, t: str) -> bool: nums = 0 for i in range(len(s)): ch = s[i]; while(nums < len(t) and t[nums] != ch): nums += 1 nums += 1 if(nums <= len(t)): return True else: return False

拓展（后续挑战）

逻辑分析：当存在大量的数据时，如果仍按照上述策略则会耗费大量的时间，所以需要我们考虑如何进行优化，而优化的方向是用空间换取时间。 在这里子问题和转移方程没有变化，变化的是寻找的方式。

数据少 通过遍历t字符串来依次寻找s字符串中的字符。

数据多 在这种情况下，我们需要在匹配前对 t 做预处理，利用一个二维数组记录每个位置的下一个要匹配的字符的位置，这里的字符是’a’ ~ ‘z’，所以这个数组的大小是 dp[26][n]，n 为 t 的长度。那么每处理一个子串只需要扫描一遍 s即可，因为在数组的帮助下我们对 t是“跳跃”扫描的。

代码

class Solution { public boolean isSubsequence(String s, String t) { // 预处理 t = " " + t; // 开头加一个空字符作为匹配入口 int n = t.length(); int[][] dp = new int[26][n]; // 记录每个位置的下一个ch的位置 for (char ch = 0; ch < 26; ch++) { int p = -1; for (int i = n - 1; i >= 0; i--) { // 从后往前记录dp dp[ch][i] = p; if (t.charAt(i) == ch + 'a') p = i; } } // 匹配 int i = 0; for (char ch : s.toCharArray()) { // 跳跃遍历 i = dp[ch - 'a'][i]; if (i == -1) return false; } return true; } }

（注：后续挑战参考@lil-p朋友的思路）