Skip to main content

判断子序列

题目

给定字符串 st, 判断 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

题解

这道题是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
}