0392. Is Subsequence

题目信息

题号:

0392

难度:

Easy

主题:

两个字符串、子序列、相对顺序、允许删除

原题:

LeetCode 0392

重点:

只能从 t 删除字符、剩余字符顺序不能改变、匹配位置必须严格递增、空字符串是任意字符串的子序列

题目重述

给定字符串 s 和 t,判断 s 是否是 t 的子序列。可以从 t 中删除任意数量的字符,也可以一个都不删除;未删除字符的相对顺序必须保持不变,最终需要恰好得到 s。

s 的长度位于 [0, 100],t 的长度位于 [0, 10^4],两个字符串只包含小写英文字母。同一个 t 中的位置不能匹配 s 的多个字符;空字符串 s 不需要匹配任何位置,因此应返回 true。

自建示例

字符可以不连续但顺序正确:

输入:s = "dog",t = "doing"
输出:true
解释:依次保留 t 中的 d、o、g,可以删除其余字符得到 dog。

所需字符出现但顺序错误:

输入:s = "god",t = "doing"
输出:false
解释:g 位于字符串末尾,在它之后无法再找到 o 和 d,因此不能保持所需顺序。

贪心匹配最早可用位置

从左到右扫描 t,维护 s 中下一个尚未匹配的字符。遇到相同字符就消耗 s 的一个位置,否则跳过 t 当前字符。选择最早出现的可匹配位置不会减少后续可用范围,因此如果连最早匹配都无法完成,任何更晚的选择也不可能完成。

C++ 实现

class Solution {
public:
    bool isSubsequence(std::string s, std::string t) {
        int index = 0;
        for (char c : t) {
            if (index < static_cast<int>(s.size())
                && s[index] == c) {
                ++index;
            }
        }
        return index == static_cast<int>(s.size());
    }
};

代码分析

index 单调向右移动,同一个 t 位置最多匹配一次;空 s 时索引初始就等于其长度,返回真。时间复杂度为 O(|t|),额外空间为 O(1)。