【面试经典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;}
};