【面试经典150题】【双指针】392. 判断子序列

题目链接

https://leetcode.cn/problems/is-subsequence/?envType=study-plan-v2&envId=top-interview-150

题解思路

1. 首先如果s的长度大于t的长度，那么s肯定不是t的子序列
2. 如果s的长度等于t的长度，那么s==t的情况下s才是t的子序列
3. 如果s的长度小于t的长度，那么我们需要一个下标i来依次遍历字符串s中的字符，另一个下标j来依次便利t中的字符，对于s[i]我们需要找到一个s[j]和它相等，对于s[i + 1]，我们需要找到t[j']和s[i + 1]相等，其中j' > j，以此类推。简单来说，我们需要按顺序遍历字符串s，然后在字符串t中找到和s中的字符相等的字符，这样才能证明s是t的子序列。
   时间复杂度$O(n+m)$
   空间复杂度$O(1)$
   附上代码：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.length();
        int m = t.length();
        // s是t的子序列的前提条件是s的长度比t短
        if (n > m) {
            return false;
        }
        // n <= m
        // 时间复杂度O(n + m)
        int j = 0;
        for (int i = 0; i < n; ++i) {
            bool match = false;
            for (;j < m; ++j) {
                if (s[i] == t[j]) {
                    match = true;
                    ++j;
                    break;
                }
            }
            if (!match) {
                return false;
            }
        }
        return true;
    }
};