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)``。