30-判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
方法一：双指针法
这是最直观的方法，通过两个指针分别遍历字符串 s 和 t，逐个比较字符。
// 判断 s 是否为 t 的子序列
function isSubsequence(s: string, t: string): boolean {
let i = 0; // 指向 s 的指针
let j = 0; // 指向 t 的指针
while (i < s.length && j < t.length) {
if (s[i] === t[j]) {
i++;
}
j++;
}
return i === s.length;
}
// 测试示例
let s1 = "ace";
let t1 = "abcde";
console.log(isSubsequence(s1, t1)); // 输出 true
let s2 = "aec";
let t2 = "abcde";
console.log(isSubsequence(s2, t2)); // 输出 false
复杂度分析
- 时间复杂度：(O(n))，其中 n 是字符串
t的长度，因为只需要遍历一次字符串t。 - 空间复杂度：(O(1))，只使用了常数级的额外空间。
方法二：递归法
通过递归的方式来判断 s 是否为 t 的子序列。
function isSubsequenceRecursive(s: string, t: string): boolean {
if (s.length === 0) {
return true;
}
if (t.length === 0) {
return false;
}
if (s[0] === t[0]) {
return isSubsequenceRecursive(s.slice(1), t.slice(1));
}
return isSubsequenceRecursive(s, t.slice(1));
}
// 测试示例
let s3 = "ace";
let t3 = "abcde";
console.log(isSubsequenceRecursive(s3, t3)); // 输出 true
let s4 = "aec";
let t4 = "abcde";
console.log(isSubsequenceRecursive(s4, t4)); // 输出 false
复杂度分析
- 时间复杂度：(O(n))，其中 n 是字符串
t的长度。在最坏情况下，需要递归 n 次。 - 空间复杂度：(O(n))，主要是递归调用栈的空间开销。
方法三：动态规划法
使用动态规划来解决这个问题，通过构建一个二维数组来记录子问题的解。
function isSubsequenceDP(s: string, t: string): boolean {
let m = s.length;
let n = t.length;
let dp: boolean[][] = new Array(m + 1).fill(false).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];
}
// 测试示例
let s5 = "ace";
let t5 = "abcde";
console.log(isSubsequenceDP(s5, t5)); // 输出 true
let s6 = "aec";
let t6 = "abcde";
console.log(isSubsequenceDP(s6, t6)); // 输出 false
复杂度分析
- 时间复杂度：(O(m * n))，其中 m 是字符串
s的长度，n 是字符串t的长度。需要填充一个 (m+1) 行 (n+1) 列的二维数组。 - 空间复杂度：(O(m * n))，主要是二维数组的空间开销。
进阶：处理大量输入的情况
当有大量输入的 S（(S_1, S_2, ... , S_k)，(k >= 10) 亿）需要依次检查它们是否为 T 的子序列时，可以采用预处理 T 的方法。具体思路是记录 T 中每个字符出现的所有位置，然后对于每个 S 中的字符，使用二分查找来找到该字符在 T 中合适的位置。
import { bisectLeft } from '@ohos.bisect';
function isSubsequenceAdvanced(s: string, t: string): boolean {
// 预处理 t，记录每个字符出现的所有位置
let charIndexes: Map<string, number[]> = new Map();
for (let i = 0; i < t.length; i++) {
let char = t[i];
if (!charIndexes.has(char)) {
charIndexes.set(char, []);
}
charIndexes.get(char)!.push(i);
}
let prevIndex = -1;
for (let char of s) {
if (!charIndexes.has(char)) {
return false;
}
let indexList = charIndexes.get(char)!;
let index = bisectLeft(indexList, prevIndex + 1);
if (index === indexList.length) {
return false;
}
prevIndex = indexList[index];
}
return true;
}
// 测试示例
let s7 = "ace";
let t7 = "abcde";
console.log(isSubsequenceAdvanced(s7, t7)); // 输出 true
let s8 = "aec";
let t8 = "abcde";
console.log(isSubsequenceAdvanced(s8, t8)); // 输出 false
复杂度分析
- 预处理时间复杂度：(O(m))，其中 m 是字符串
t的长度。需要遍历一次字符串t来记录每个字符出现的位置。 - 每个
S的检查时间复杂度：(O(k log m))，其中 k 是字符串S的长度，m 是字符串t的长度。对于S中的每个字符，需要进行一次二分查找。 - 空间复杂度：(O(m))，主要用于存储每个字符出现的位置。
通过这种方式，可以在处理大量输入时提高效率。