392. 判断子序列 Easy

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

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

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false

解题思路

输入：两个字符串 s t

输出：判断 s 是否为 t 的子序列

本题属于 同向双指针 问题

我们可以用两个指针同时从两个字符串左侧开始遍历

当左右两个指针对应的字符相等时，左指针（指向 s 的指针）向右移动

不论是否匹配，右指针（指向 t 的指针）向右移动

最后判断左指针是否已经遍历完 s 字符串即可

代码实现

python

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 特殊情况处理：如果 s 比 t 长，肯定不是子序列
        if len(s) > len(t):
            return False
        
        # 双指针法
        i, j = 0, 0  # i 指向 s，j 指向 t

        # 遍历 t，匹配 s 中的字符
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                # 匹配到一个字符，i 往前移动
                i += 1
            # 无论是否匹配成功，j 都要往前走
            j += 1

        # 如果 i 走完了 s，说明全部字符都匹配成功
        return i == len(s)

javascript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let l = 0;
    let r = 0;

    while (l < s.length && r < t.length) {
        if (s[l] == t[r]) {
            l ++;
        }
        r++;
    }

    return l === s.length;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

392 国际版

392 中文版