判断子序列

#2024/07/28 #算法/双指针 #leetcode

目录

• 题目及理解
• 解题思路
• 代码实现
  • 复杂度分析
• 进阶
• 错误记录

题目及理解

解题思路

• 使用快慢指针遍历
• 遍历完后看慢指针是否等于子序列的长度

代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  let slow = 0; // 慢指针
  let fast = 0; // 快指针

  // 使用快慢指针，遍历字符串 t
  while (fast < t.length) {
    // 当 s[slow] 与 t[fast] 相等时，慢指针向后移动一位
    if (s[slow] === t[fast]) {
      slow++;
    }
    // 快指针向后移动一位，正常速度移动
    fast++;
  }
  // 如果慢指针的值等于 s 的长度，说明 s 是 t 的子序列
  return slow === s.length;
};

复杂度分析

进阶

比较困难，详细题解：二分查找高效判定子序列

错误记录