31-判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 进阶： 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

方法一：双指针法

双指针法是一种直观且高效的方法，通过分别使用两个指针遍历字符串 s 和 t，比较对应字符，若匹配则移动 s 的指针，无论是否匹配都移动 t 的指针，最后判断 s 的指针是否到达末尾。

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++;}j++;}return i === s.length;
}

复杂度分析

• 时间复杂度：(O(n))，其中 n 是字符串 t 的长度。因为只需要遍历一次字符串 t。
• 空间复杂度：(O(1))，只使用了常数级的额外空间，用于存储两个指针。

方法二：递归法

递归法通过不断缩小问题规模，比较当前字符是否相等，若相等则递归判断剩余部分，若不相等则只递归处理 t 的剩余部分，直到 s 为空或者 t 为空。

function isSubsequence(s: string, t: string): boolean {if (s.length === 0) {return true;}if (t.length === 0) {return false;}if (s[0] === t[0]) {return isSubsequence(s.slice(1), t.slice(1));}return isSubsequence(s, t.slice(1));
}

复杂度分析

• 时间复杂度：(O(n))，其中 n 是字符串 t 的长度。在最坏情况下，每次递归调用都会处理 t 的一个字符。
• 空间复杂度：(O(n))，主要是递归调用栈的空间开销，递归深度最大为 t 的长度。

方法三：动态规划法

动态规划法通过构建一个二维数组 dp 来记录子问题的解，dp[i][j] 表示 s 的前 i 个字符是否是 t 的前 j 个字符的子序列，根据字符是否相等进行状态转移。

function isSubsequence(s: string, t: string): boolean {const m = s.length;const n = t.length;const dp: boolean[][] = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(false));for (let j = 0; j <= n; j++) {dp[0][j] = true;}for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {if (s[i - 1] === t[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = dp[i][j - 1];}}}return dp[m][n];
}

复杂度分析

• 时间复杂度：(O(m * n))，其中 m 是字符串 s 的长度，n 是字符串 t 的长度。需要填充一个 (m+1) 行 (n+1) 列的二维数组。
• 空间复杂度：(O(m * n))，主要用于存储二维数组 dp。

进阶问题思路

当有大量输入的 S（如 S1, S2, ... , Sk 其中 (k >= 10) 亿）需要依次检查它们是否为 T 的子序列时，双指针法的时间复杂度会很高，因为每次都要重新遍历 T。可以使用预处理 T 的方法，记录每个字符在 T 中出现的所有位置，然后对于每个输入的 S，使用二分查找来快速定位字符在 T 中的位置，这样可以将每次判断的时间复杂度降低到 (O(m * log n))，其中 m 是 S 的长度，n 是 T 的长度。以下是实现代码：

function preprocess(t: string): number[][] {const pos: number[][] = new Array(26).fill(0).map(() => []);for (let i = 0; i < t.length; i++) {const index = t.charCodeAt(i) - 'a'.charCodeAt(0);pos[index].push(i);}return pos;
}function isSubsequenceAdvanced(s: string, t: string, pos: number[][]): boolean {let prev = -1;for (let i = 0; i < s.length; i++) {const index = s.charCodeAt(i) - 'a'.charCodeAt(0);const charPos = pos[index];let left = 0;let right = charPos.length - 1;let found = false;while (left <= right) {const mid = Math.floor((left + right) / 2);if (charPos[mid] > prev) {right = mid - 1;prev = charPos[mid];found = true;} else {left = mid + 1;}}if (!found) {return false;}}return true;
}// 示例使用
const t = "abcde";
const pos = preprocess(t);
const s = "ace";
console.log(isSubsequenceAdvanced(s, t, pos));

这种方法通过预处理 T 减少了重复计算，提高了处理大量输入时的效率。