判断子序列
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
题解
这道题是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
}