题目描述

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

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

样例

示例 1：

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

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

暴力匹配 O(n^2)

暴力写法就是双层循环，没有为什么，哈哈，具体的东西，代码里面解释。

C++ 暴力代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(),m = t.size();
        if (n == 0) return true; // 没有元素都是对的，因为t数组可以删除直到跟s一样 
        for (int i = 0;i < m;i ++){ //根据t数组来当遍历
        // 当t数组种可存在 s的时候，我们就进入第二层循环，遍历一遍 ，存在则true
            if(t[i] == s[0]) {
                int cnt = 1;
                for (int j = i + 1;j < m;j ++){
                     if (t[j] == s[cnt]) cnt++;
                    if (cnt == n) return true; // 优化而已
                }
            }
        }
        return false;
    }
};

单调性 O(n)

我想说有看到标题懵逼的吗?
为什么会说单调性？
因为 我个人觉得在匹配的时候，只会向右。单调增。
那么我们在实现代码的时候，t数组会一直向右移动，s数组是在当前一个元素被匹配的时候，s数组指针向右移动

C++ 代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(),m = t.size();
        if (n == 0) return true;
        int cnt = 0;
        for (int i = 0;i < m;i ++){
           if (s[cnt] == t[i]) cnt ++;
           if (cnt == n) return true; // 优化，当真的存在，就返回答案
        }
        return false;
    }
};