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``。 自建示例 -------- 字符可以不连续但顺序正确: .. code-block:: text 输入:s = "dog",t = "doing" 输出:true 解释:依次保留 t 中的 d、o、g,可以删除其余字符得到 dog。 所需字符出现但顺序错误: .. code-block:: text 输入:s = "god",t = "doing" 输出:false 解释:g 位于字符串末尾,在它之后无法再找到 o 和 d,因此不能保持所需顺序。 贪心匹配最早可用位置 ---------------------- 从左到右扫描 ``t``,维护 ``s`` 中下一个尚未匹配的字符。遇到相同字符就消耗 ``s`` 的一个位置,否则跳过 ``t`` 当前字符。选择最早出现的可匹配位置不会减少后续可用范围,因此如果连最早匹配都无法完成,任何更晚的选择也不可能完成。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool isSubsequence(std::string s, std::string t) { int index = 0; for (char c : t) { if (index < static_cast(s.size()) && s[index] == c) { ++index; } } return index == static_cast(s.size()); } }; 代码分析 -------- ``index`` 单调向右移动,同一个 ``t`` 位置最多匹配一次;空 ``s`` 时索引初始就等于其长度,返回真。时间复杂度为 ``O(|t|)``,额外空间为 ``O(1)``。