不同的子序列
解题思路：
-
记 m=len(t), n=len(s)，创建二维数组 dp(m+1)⋅(n+1) ，其中 dp[i][j] 表示 t 的前 i 个连续字符（即 t[:i]）在 s 的前 j 个字符（即 s[:j]]）中出现的个数；
-
初始化：
- dp[i][0] =1，当j=0时，相当于t是空字符串，空字符在另一个字符串的子串中出现一次，此时第一列都初始化为1；
- 其他情况，初始化的时候dp[i][j] =0；
-
状态转移（行遍历）：
- 当 t[i-1] !== s[j-1] 时：相当于 s 中新加入的第 j 个字符 s[j-1] 没有起到作用；因此：dp[i][j]=dp[i][j−1]；
- 当 t[i-1] === s[j-1]时，则存在两种模式：
- 考虑 t[i-1] 与 s[j-1] 匹配，对应 t[:i-1] 和 s[:j-1] 匹配的数目 dp[i−1][j−1]；
- 不考虑 t[i-1] 与 s[j-1] 匹配，相当于 s[j-1] 没有起到作用，对应 dp[i][j-1]；
- 最终的状态转移方程如下：
- t[i-1] !== s[j-1]：dp[i][j] = dp[i][j−1]；
- t[i-1] === s[j-1]：dp[i][j] = dp[i−1][j−1] + dp[i][j-1]；
复杂度：
-
时间复杂：度O(mn)，m，n分别是s和t的长度；
-
空间复杂度：O(mn)，dp数组的空间；
代码实现：
var numDistinct = function (s, t) {
const sLen = s.length,tLen = t.length
dp = new Array(sLen + 1)
for (let i = 0; i < sLen + 1; i++) {
dp[i] = new Array(tLen + 1).fill(0)
}
for (let i = 0; i < sLen + 1; i++) {
for (let j = 0; j < tLen + 1; j++) {
if (j == 0) {
dp[i][j] = 1
} else if (i == 0) {
dp[i][j] = 0
} else {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
} else {
dp[i][j] = dp[i - 1][j]
}
}
}
}
return dp[sLen][tLen]
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
583.两个字符串的删除操作
上一篇
评论
