app开发公司办公室设计_权威发布的图片_北京建站工作室_论坛软文案例

不同的子序列

• https://leetcode.cn/problems/distinct-subsequences/description/

描述

• 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1

输入：s = "rabbbit", t = "rabbit"
输出：3

解释：
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit

示例 2

输入：s = "babgbag", t = "bag"
输出：5

解释：
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

Typescript 版算法实现

1 ) 方案1

function numDistinct(s: string, t: string): number {const m = s.length, n = t.length;if (m < n) {return 0;}const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));for (let i = 0; i <= m; i++) {dp[i][n] = 1;}for (let i = m - 1; i >= 0; i--) {for (let j = n - 1; j >= 0; j--) {if (s[i] == t[j]) {dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];} else {dp[i][j] = dp[i + 1][j];}}}return dp[0][0];
};

2 ) 方案2：递归(无记忆化)

function numDistinct(s: string, t: string): number {const sLen = s.length, tLen = t.lengthfunction helper(i, j) {if (j < 0) return 1if (i < 0) return 0if (s[i] == t[j]) {return helper(i-1, j) + helper(i-1, j-1)}return helper(i-1, j)}return helper(sLen-1, tLen-1) 
}

• LeetCode 超时

3 ) 方案3：递归 (记忆化)

function numDistinct(s: string, t: string): number {const sLen = s.length, tLen = t.length, memo = new Array(sLen)for (let i = 0; i < sLen; i++) {memo[i] = new Array(tLen)for (let j = 0; j < tLen; j++) {memo[i][j] =  -1}}function helper(i, j) {if (j < 0) return 1if (i < 0) return 0if (memo[i][j] !=  -1) { return memo[i][j]}if (s[i] == t[j]) {memo[i][j] = helper(i-1, j) + helper(i-1, j-1)} else {memo[i][j] = helper(i-1, j)}return memo[i][j]}return helper(sLen-1, tLen-1) 
};

4 ) 方案4: 动态规划

function numDistinct(s: string, t: string): number {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]
}