[392] 判断子序列

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

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

示例 1：

输入：s = "abc", t = "ahbgdc"

输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"

输出：false

提示：

两个字符串都只由小写字符组成。

说实话这道题目的标签和题目描述属实把我误导的好惨，一看到动态规划，再一看子序列问题，简单啊，二维dp字符串比较走起，很轻松就 ac 了代码。

function isSubsequence(s: string, t: string): boolean {
  const sLen = s.length;
  const tLen = t.length;
  if (sLen > tLen) return false;
  const dp: number[][] = Array(sLen + 1)
    .fill(0)
    .map(x => Array(tLen + 1).fill(0));
  // 字串s为空字符串时，恒成立
  for (let j = 0; j <= tLen; j++) {
    dp[0][j] = 1;
  }
  for (let i = 1; i <= sLen; i++) {
    for (let j = i; j <= tLen; j++) {
      // 如果不包含该字符的t的字串已经成立，则加上当前字符仍然成立
      if (dp[i][j - 1]) {
        dp[i][j] = 1;
      }
      // 如果两字符相等，且不包含两字符的各自字串符合条件，则当前情况也成立
      else if (s[i - 1] === t[j - 1] && dp[i - 1][j - 1]) {
        dp[i][j] = 1;
      }
    }
  }
  return !!dp[sLen][tLen];
}

但是后面再一次回看题目，淦，不对啊，这里只需要对两字符串用双指针，字符串各遍历一次就完成了呀。根本就不需要O(M*N)的复杂度，O(M+N)就搞定了呀！

function isSubsequence(s: string, t: string): boolean {
  let i = 0;
  let j = 0;
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) {
      i += 1;
      j += 1;
    } else {
      j += 1;
    }
  }
  return i === s.length;
}