392.判断子序列

【LetMeFly】392.判断子序列

力扣题目链接：https://leetcode.cn/problems/is-subsequence/

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

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

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 

示例 1：

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

示例 2：

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

 

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

方法一：双指针

使用“指针”loct来记录字符串t处理到到了哪个元素

之后用“指针”locs遍历一遍字符串s

在loct在合法范围内时，不断后移loct，直到t[loct]等于s[locs]

中间过程中，但凡loct超出合法范围，就返回false

若t中每个元素都在s中找到了对应位置（遍历结束），就返回true

• 时间复杂度$O(len(s) + len(t))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    bool isSubsequence(string& s, string& t) {
        int loct = 0;
        for (int locs = 0; locs < s.size(); locs++) {
            while (loct < t.size() && t[loct] != s[locs])
                loct++;
            if (loct == t.size())
                return false;
            loct++;
        }
        return true;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127279017