0392. Is Subsequence¶
题目信息¶
- 题号:
0392
- 难度:
Easy
- 主题:
两个字符串、子序列、相对顺序、允许删除
- 原题:
- 重点:
只能从
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)。