392. 判断子序列

解题过程

INFO

题目链接给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。进阶：如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

javascript

/**
 * @link https://leetcode.cn/problems/is-subsequence/
 * @title 392. 判断子序列
 * @description 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

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

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
// 解法一
// 思路：类似双指针思维，遍历 s 字符串，然后在 t 字符串里面查找对应出现相同的字符并记录次数，最后判断记录的次数是否跟 s 字符串长度相等即可
var isSubsequence = function (s, t) {
  let res = 0
  let currentIndex = 0
  for (let i = 0; i < s.length; i++) {
    for (let j = currentIndex; j < t.length; j++) {
      if (s[i] === t[j]) {
        currentIndex = j + 1
        res++
        break
      }
    }
  }

  return res === s.length
};

// 解法二
// 思路：优化解法一双指针代码
var isSubsequence = function (s, t) {
  let total = currentIndex = 0

  while (total < s.length && currentIndex < t.length) {
    if (s[total] === t[currentIndex]) {
      total++
    }

    currentIndex++
  }

  return total === s.length
}

// 解法三
// 思路：题解评论区 Java 解法——方向思维：遍历 s 字符串然后根据查找 t 累积存在对应字符串索引位置的值累加下次进行遍历，查找不存在直接返回 false
var isSubsequence = function (s, t) {
  let currentIndex = -1
  for (let i = 0; i < s.length; i++) {
    currentIndex = t.indexOf(s[i], currentIndex + 1)

    if (currentIndex === -1) {
      return false
    }
  }

  return true
}

const result = isSubsequence ('abc', 'ahbgdc') // true
// const result = isSubsequence ('axc', 'ahbgdc') // false
// const result = isSubsequence("aaaaaa", "bbaaaa") // false
console.log(result)

解题感受

双指针解法就很简单，只需动态遍历判断 s 和 t 字符串累积相等的值的次数是否等于 s 的长度即可。看了官方题解是可以用动态规划来做的，但是动态规划自己不熟悉还没学对应的理论知识和实践类型的题目

392. 判断子序列 ​

解题过程 ​

解题感受 ​

优质题解 ​

392. 判断子序列

解题过程

解题感受

优质题解