数据结构与算法之动态规划: LeetCode 115. 不同的子序列 (Ts版) ...

不同的子序列

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

描述

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

示例 1

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

复制代码

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

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

复制代码

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

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

Typescript 版算法实现


1 ) 方案1

1. function numDistinct(s: string, t: string): number {
2.     const m = s.length, n = t.length;
3.     if (m < n) {
4.         return 0;
5.     }
6.     const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
7.     for (let i = 0; i <= m; i++) {
8.         dp[i][n] = 1;
9.     }
10.     for (let i = m - 1; i >= 0; i--) {
11.         for (let j = n - 1; j >= 0; j--) {
12.             if (s[i] == t[j]) {
13.                 dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
14.             } else {
15.                 dp[i][j] = dp[i + 1][j];
16.             }
17.         }
18.     }
19.     return dp[0][0];
20. };

复制代码

2 ) 方案2：递归(无影象化)

1. function numDistinct(s: string, t: string): number {
2.         const sLen = s.length, tLen = t.length
3.        
4.         function helper(i, j) {
5.                 if (j < 0) return 1
6.                 if (i < 0) return 0
7.                 if (s[i] == t[j]) {
8.                         return helper(i-1, j) + helper(i-1, j-1)
9.                 }
10.         return helper(i-1, j)
11.         }
12.         return helper(sLen-1, tLen-1)
13. }

复制代码

• LeetCode 超时
  

3 ) 方案3：递归 (影象化)

1. function numDistinct(s: string, t: string): number {
2.         const sLen = s.length, tLen = t.length, memo = new Array(sLen)
3.         for (let i = 0; i < sLen; i++) {
4.                 memo[i] = new Array(tLen)
5.                 for (let j = 0; j < tLen; j++) {
6.                         memo[i][j] =  -1
7.                 }
8.         }
9.         function helper(i, j) {
10.                 if (j < 0) return 1
11.                 if (i < 0) return 0
12.                 if (memo[i][j] !=  -1) {
13.                         return memo[i][j]
14.                 }
15.                 if (s[i] == t[j]) {
16.                         memo[i][j] = helper(i-1, j) + helper(i-1, j-1)
17.                 } else {
18.                         memo[i][j] = helper(i-1, j)
19.                 }
20.                 return memo[i][j]
21.         }
22.         return helper(sLen-1, tLen-1)
23. };

复制代码

4 ) 方案4: 动态规划

1. function numDistinct(s: string, t: string): number {
2.         const sLen = s.length, tLen = t.length, dp = new Array(sLen+1)
3.         for (let i = 0; i < sLen+1; i++) {
4.                 dp[i] = new Array(tLen+1).fill(0)
5.         }
6.         for (let i = 0; i < sLen+1; i++) {
7.                 for (let j = 0; j < tLen+1; j++) {
8.                         if (j == 0) {               
9.                                 dp[i][j] = 1
10.                         } else if (i == 0) {
11.                                 dp[i][j] = 0
12.                         } else {                       
13.                                 if (s[i-1] == t[j-1]) {
14.                                         dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
15.                                 } else {
16.                                         dp[i][j] = dp[i-1][j]
17.                                 }
18.                         }
19.                 }
20.         }
21.         return dp[sLen][tLen]
22. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。