判断子序列

Tips

题目类型: Dynamic Programming

题目

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

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

进阶:

如果有大量输入的 S, 称作 S1, S2, ... , Sₖ 其中 k >= 10亿, 你需要依次检查它们是否为 T 的子序列. 在这种情况下, 你会怎样改变代码?

提示:

0 <= s.length <= 100
0 <= t.length <= 10⁴
两个字符串都只由小写字符组成.

示例

输入: s = "abc", t = "ahbgdc"
输出: true

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

题解

JavaScript - 双指针
JavaScript - 动态规划

性价比最好的做法就是双指针, 但一开始可能会想到用哈希表, 也没毛病.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  const m = s.length
  const n = t.length
  let sIdx = 0
  let tIdx = 0

  while (tIdx < t.length) {
    if (s[sIdx] === t[tIdx]) {
      sIdx++
    }
    tIdx++
  }

  return sIdx === s.length
}

用动态规划的方式对于本题并不划算, 但本题是 72. 编辑距离的预热题, 如果匹配不到, 相当于要把 t 中对应的字符串删掉, 那就是 dp[i][j] = dp[i][j - 1]

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  const m = s.length
  const n = t.length
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = dp[i][j - 1]
      }
    }
  }

  return dp[m][n] === m
}

题目​

题解​

题目

题解