#判断子序列

#题目描述

给定字符串 s 和 t，判断 s 是否为 t 的子序列。

字符串的子序列是指：通过删除原字符串中的一些（或不删除）字符，在不改变剩余字符相对位置的情况下，得到的新字符串。

示例 1：

• 输入：s = "abc"，t = "ahbgdc"
• 输出：true
• 说明："abc" 是 "ahbgdc" 的子序列（依次找到 a、b、c）

示例 2：

• 输入：s = "axc"，t = "ahbgdc"
• 输出：false
• 说明：t 中无法按顺序找到 "axc"（有 a 和 c，但中间没有 x）

#思路分析

这是一道经典的双指针问题，核心思想是：在 t 中按顺序寻找 s 的每个字符。

#双指针策略

使用两个指针分别指向 s 和 t 的当前位置：

• 指针 i：指向 s 的当前待匹配字符
• 指针 j：指向 t 的当前字符

#移动规则

1. 当 s[i] === t[j] 时：

   • 说明在 t 中找到了 s 的当前字符
   • i 指针前移（继续匹配 s 的下一个字符）
   • j 指针前移（继续在 t 中搜索）

2. 当 s[i] !== t[j] 时：

   • 当前字符不匹配
   • i 指针不动（继续寻找当前字符）
   • j 指针前移（在 t 的后续字符中继续搜索）

3. 终止条件：

   • 若 i 遍历完 s（i === s.length），说明 s 的所有字符都在 t 中按顺序找到了，返回 true
   • 若 j 遍历完 t 而 i 还没遍历完 s，说明 t 中无法找到 s 的所有字符，返回 false

#算法步骤

1. 初始化两个指针：i = 0（指向 s），j = 0（指向 t）
2. 当 i < s.length 且 j < t.length 时循环：
   • 若 s[i] === t[j]，则 i++（匹配成功，继续匹配下一个）
   • j++（无论是否匹配，t 的指针始终前移）
3. 循环结束后，返回 i === s.length（判断 s 是否完全匹配）

#关键点

• j 指针始终前移：这是算法的核心，确保遍历整个 t 字符串
• i 指针按需前移：仅在字符匹配时才前移，记录匹配进度
• 最终判断：检查 i 是否到达 s 的末尾，而不是检查 j 是否到达 t 的末尾

#示例代码

/**
 * 判断 s 是否是 t 的子序列
 * 使用双指针法：依次在 t 中寻找 s 的每个字符，保持相对顺序
 * 
 * @param s - 待检查的子序列字符串
 * @param t - 源字符串
 * @returns 如果 s 是 t 的子序列返回 true，否则返回 false
 * 
 * @example
 * isSubsequence("abc", "ahbgdc") // true
 * isSubsequence("axc", "ahbgdc") // false
 */
export function isSubsequence(s: string, t: string): boolean {
    let i = 0, j = 0; // i 指向 s 的当前字符，j 指向 t 的当前字符

    // 同时遍历 s 和 t，直到其中一个遍历完
    while (i < s.length && j < t.length) {
        // 如果当前字符匹配
        if (s[i] === t[j]) {
            i++; // s 指针前移，继续匹配下一个字符
        }
        j++; // t 指针始终前移，继续在 t 中寻找
    }

    // 循环结束后，检查 s 是否已完全匹配
    return i === s.length;
}

#复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 t 的长度。最坏情况下需要遍历整个 t 字符串。
• 空间复杂度：O(1)，只使用了两个指针变量。

#示例演示

#示例 1：s = "abc", t = "ahbgdc"

结果：i === s.length 为 true，返回 true

#示例 2：s = "axc", t = "ahbgdc"

结果：i === 1 !== s.length（s.length === 3），返回 false

#示例 3：空字符串 s = "", t = "ahbgdc"

结果：循环条件不满足，直接返回 i === s.length 为 true（空字符串是任何字符串的子序列）